发布时间 : 星期三 文章南邮通达2015数据结构B刷题试题及答案更新完毕开始阅读58edaf846c85ec3a86c2c560
３．
在链式存储结构上设计直接插入排序算法
在链式存储结构上设计直接插入排序算法
void straightinsertsort(lklist *&head) {
lklist *s,*p,*q; int t;
if (head==0 || head->next==0) return;
else for(q=head,p=head->next;p!=0;p=q->next) {
for(s=head;s!=q->next;s=s->next) if (s->data>p->data) break; if(s==q->next)q=p;
else{q->next=p->next; p->next=s->next; s->next=p;
t=p->data;p->data=s->data;s->data=t;}
} }
25
数据结构试卷（七）
一、选择题(30分)
1．设某无向图有n个顶点，则该无向图的邻接表中有（ ）个表头结点。 (A) 2n
(B) n
(C) n/2
(D) n(n-1)
2．设无向图G中有n个顶点，则该无向图的最小生成树上有（ ）条边。 (A) n
(B) n-1
(C) 2n
(D) 2n-1
3．设一组初始记录关键字序列为(60，80，55，40，42，85)，则以第一个关键字45为基准而得到的一趟快速排序结果是（ ）。
(A) 40，42，60，55，80，85 (C) 42，40，55，60，80，85
(B) 42，45，55，60，85，80 (D) 42，40，60，85，55，80
4．（ ）二叉排序树可以得到一个从小到大的有序序列。
(A) 先序遍历
(B) 中序遍历 (C) 后序遍历 (D) 层次遍历
5．设按照从上到下、从左到右的顺序从1开始对完全二叉树进行顺序编号，则编号为i结点的左孩子结点的编号为（ ）。
(A) 2i+1
(B) 2i
(C) i/2
(D) 2i-1
6．程序段s=i=0；do {i=i+1； s=s+i；}while(i<=n)；的时间复杂度为（ ）。
(A) O(n)
(B) O(nlog2n)
(C) O(n2)
(D) O(n3/2)
7．设带有头结点的单向循环链表的头指针变量为head，则其判空条件是（ ）。
(A) head==0
(C) head->next==head
(B) head->next==0 (D) head!=0
8．设某棵二叉树的高度为10，则该二叉树上叶子结点最多有（ ）。 (A) 20
(B) 256
(C) 512
(D) 1024
9．设一组初始记录关键字序列为(13，18，24，35，47，50，62，83，90，115，134),则利用二分法查找关键字90需要比较的关键字个数为（ ）。 (A) 1
(B) 2
(C) 3
(D) 4
10.设指针变量top指向当前链式栈的栈顶，则删除栈顶元素的操作序列为（ ）。
26
(A) top=top+1; (C) top->next=top; (B) top=top-1;
(D) top=top->next;
四、算法设计题(20分)
1. 设计在链式结构上实现简单选择排序算法。 设计在链式结构上实现简单选择排序算法。
void simpleselectsorlklist(lklist *&head) {
lklist *p,*q,*s; int min,t;
if(head==0 ||head->next==0) return; for(q=head; q!=0;q=q->next) {
min=q->data; s=q;
for(p=q->next; p!=0;p=p->next) if(min>p->data){min=p->data; s=p;} if(s!=q){t=s->data; s->data=q->data; q->data=t;} } }
2. 设计在顺序存储结构上实现求子串算法。 设计在顺序存储结构上实现求子串算法。
void substring(char s[ ], long start, long count, char t[ ]) {
long i,j,length=strlen(s);
if (start<1 || start>length) printf(\ else if (start+count-1>length) printf(\else { for(i=start-1,j=0; i 3. 设计求结点在二叉排序树中层次的算法。 设计求结点在二叉排序树中层次的算法。 int lev=0; typedef struct node{int key; struct node *lchild,*rchild;}bitree; void level(bitree *bt,int x) { if (bt!=0) {lev++; if (bt->key==x) return; else if (bt->key>x) level(bt->lchild,x); else level(bt->rchild,x);} } 27 28