发布时间 : 星期六 文章南邮通达2015数据结构B刷题试题及答案更新完毕开始阅读58edaf846c85ec3a86c2c560
if(ha->data
else {if(s==0) hc=s=hb; else {s->next=hb; s=hb;};hb=hb->next;} if(ha==0) s->next=hb; else s->next=ha; }
21
数据结构试卷(六)
一、选择题(30分)
1. 设一组权值集合W={2,3,4,5,6},则由该权值集合构造的哈夫曼树中
带权路径长度之和为( )。 (A) 20
(B) 30
(C) 40
(D) 45
2.执行一趟快速排序能够得到的序列是( )。
(A) [41,12,34,45,27] 55 [72,63] (B) [45,34,12,41] 55 [72,63,27] (C) [63,12,34,45,27] 55 [41,72] (D) [12,27,45,41] 55 [34,63,72]
3.设一条单链表的头指针变量为head且该链表没有头结点,则其判空条件是( )。
(A) head==0 (C) head->next==head
(B) head->next==0 (D) head!=0
4.时间复杂度不受数据初始状态影响而恒为O(nlog2n)的是( )。
(A) 堆排序
(B) 冒泡排序 (C) 希尔排序 (D) 快速排序
5.设二叉树的先序遍历序列和后序遍历序列正好相反,则该二叉树满足的条件是( )。
(A) 空或只有一个结点 (C) 任一结点无左孩子
(B) 高度等于其结点数 (D) 任一结点无右孩子
6.一趟排序结束后不一定能够选出一个元素放在其最终位置上的是( )。
(A) 堆排序
(B) 冒泡排序 (C) 快速排序 (D) 希尔排序
7.设某棵三叉树中有40个结点,则该三叉树的最小高度为( )。 (A) 3
(B) 4
(C) 5
22
(D) 6
8.顺序查找不论在顺序线性表中还是在链式线性表中的时间复杂度为( )。
(A) O(n)
(B) O(n2)
(C) O(n1/2)
(D) O(1og2n)
9.二路归并排序的时间复杂度为( )。
(A) O(n)
(B) O(n2)
(C) O(nlog2n) (D) O(1og2n)
10. 深度为k的完全二叉树中最少有( )个结点。
(A) 2k-1-1
(B) 2k-1
(C) 2k-1+1
(D) 2k-1
11.设指针变量front表示链式队列的队头指针,指针变量rear表示链式队列的队
尾指针,指针变量s指向将要入队列的结点X,则入队列的操作序列为( )。
(A) front->next=s;front=s; (C) rear->next=s;rear=s;
(B) s->next=rear;rear=s; (D) s->next=front;front=s;
12.设某无向图中有n个顶点e条边,则建立该图邻接表的时间复杂度为( )。
(A) O(n+e)
(B) O(n2)
(C) O(ne)
(D) O(n3)
13.设某哈夫曼树中有199个结点,则该哈夫曼树中有( )个叶子结点。 (A) 99
(B) 100
(C) 101
(D) 102
14.设二叉排序树上有n个结点,则在二叉排序树上查找结点的平均时间复杂度
为( )。
(A) O(n)
(B) O(n2)
(C) O(nlog2n)
(D) O(1og2n)
15.设用邻接矩阵A表示有向图G的存储结构,则有向图G中顶点i的入度为
( )。
四、算法设计题(20分) 1.
设计在顺序有序表中实现二分查找的算法。
(A) 第i行非0元素的个数之和 (B) 第i列非0元素的个数之和 (C) 第i行0元素的个数之和
(D) 第i列0元素的个数之和
设计在顺序有序表中实现二分查找的算法。
struct record {int key; int others;};
int bisearch(struct record r[ ], int k)
23
{
int low=0,mid,high=n-1; while(low<=high) {
mid=(low+high)/2;
if(r[mid].key==k) return(mid+1); else if(r[mid].key>k) high=mid-1; else low=mid+1;
}
return(0); } 2.
设计判断二叉树是否为二叉排序树的算法。
设计判断二叉树是否为二叉排序树的算法。
int minnum=-32768,flag=1;
typedef struct node{int key; struct node *lchild,*rchild;}bitree; void inorder(bitree *bt) { if (bt!=0) {inorder(bt->lchild); if(minnum>bt->key)flag=0; minnum=bt->key;inorder(bt->rchild);} }
24