北京理工大学-数据结构期末考试试题（六）
数据结构试卷（六）
一、选择题(30分)
给定一组权值集合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]
假设有一条单链表的头指针变量名为head且该链表不带头结点，则其判空条件是什么？
(A)head==0 (B) head->next==0
(C)head->next==head (D)head!=0
4．时间复杂度不受数据初始状态影响而恒为O(nlog2n)的是（ ）。
(A)堆排序 (B) 冒泡排序 (C) 希尔排序 (D) 快速排序
5．设某二叉树T的先、后序遍历次序与常规情况正相反而已，则该T必须具备以下特征：一是其根节点必须只有一个子节点；二是左右子树均为叶子节点；三是整个结构必形成一条直线。请判断T是否符合这一条件。
(A)空或只有一个结点 (B) 高度等于其结点数
(C)任一结点无左孩子 (D) 任一结点无右孩子
6．一趟排序结束后不一定能够选出一个元素放在其最终位置上的是（ ）。
(A)堆排序 (B) 冒泡排序 (C) 快速排序 (D) 希尔排序
7．设某棵三叉树中有40个结点，则该三叉树的最小高度为（ ）。
(A)3 (B) 4 (C) 5 (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
令front为链表队头的指针变量, rear用于指向链表末尾的位置.当有一个结点s需要插入到该链表中时,则入队操作按照以下步骤进行:首先将s的数据域复制到尾部存储空间中,并更新rear指向新数据位置.
(A) front->next=s；front=s； (B) s->next=rear；rear=s；
(C)rear->next=s；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
给定一个包含n个节点的二叉排序树，则其平均时间性能为（ ）。
(A)O(n) (B) O(n2) (C) O(nlog2n) (D) O(1og2n)
15.设用邻接矩阵A表示有向图G的存储结构，则有向图G中顶点i的入度为（ ）。
(A)第i行非0元素的个数之和 (B)第i列非0元素的个数之和
(C) 第i行0元素的个数之和 (D) 第i列0元素的个数之和
二、判断题(20分)
1．调用一次深度优先遍历可以访问到图中的所有顶点。（ ）
2．分块查找的平均查找长度不仅与索引表的长度有关，而且与块的长度有关。（ ）
3．冒泡排序在初始关键字序列为逆序的情况下执行的交换次数最多。（ ）
4．满二叉树一定是完全二叉树，完全二叉树不一定是满二叉树。（ ）
5．给定一棵二叉树的前序遍历序列和后序遍历序列，则可唯一确定该二叉树的具体形态。（√）
6．层次遍历初始堆可以得到一个有序的序列。（ ）
7．设一棵树T可以转化成二叉树BT，则二叉树BT中一定没有右子树。（ ）
8．线性表的顺序存储结构比链式存储结构更好。（ ）
9．中序遍历二叉排序树可以得到一个有序的序列。（ ）
10.快速排序是排序算法中平均性能最好的一种排序。（ ）
三、填空题(30分)
1．for(i=1，t=1，s=0；i<=n；i++){t=t*i；s=s+t；}的时间复杂度为_________。
令指针变量p指示单链表中的结点A，并指示被插入的新结点X，则执行插入操作所需的语句顺序为__________________________（设各节点的指针域为next）。
设有一个有向图G采用二元组形式表示为G=（V,E），其中V={1,2,3,4,5}；E是一个包含单一关系r的关系集；而关系r具体由以下有序对组成：{<1→2>, <2→4>, <4→5>, <1→3>, <3→2>, <3→5>}。请给出该有向图的一种有效的拓扑排序序列__________。
4．设无向图G中有n个顶点，则该无向图中每个顶点的度数最多是_________。
假设该二叉树中所有度为零的节点总数为50；所有度为一的节点总数为30；那么该二叉树中的总节点数量是多少？
令F和R分别为顺序循环队列的头部和尾部指针，则判断该顺序循环队列为零状态的状态条件是什么
在二叉树结构中，每个节点都设有lchild和rchild两个指针域。判定指针变量p所指向的节点为叶子节点的必要条件是：且p所指节点同时没有左、右孩子指向其他子树。
8．简单选择排序和直接插入排序算法的平均时间复杂度为___________。
9．快速排序算法的空间复杂度平均情况下为__________，最坏的情况下为__________。
10.散列表中解决冲突的两种方法是_____________和_____________。
四、算法设计题(20分)
１．设计在顺序有序表中实现二分查找的算法。
２．设计判断二叉树是否为二叉排序树的算法。
３．在链式存储结构上设计直接插入排序算法。
参考答案
一、选择题
1．D 2．A 3．A 4．A 5．D
6．D 7．B 8．A 9．C 10．B
11．C 12．A 13．B 14．D 15．B
二、判断题
1．错 2．对 3．对 4．对 5．错
6．错 7．对 8．错 9．对 10．对
三、填空题
1. O(n)
2. s->next=p->next;p->next=s
3. (1，3，2，4，5)
4. n-1
5. 129
6. F==R
7. p->lchild==0&&p->rchild==0
8. O(n2)
9. O(nlog2n)， O(n)
10. 开放定址法，链地址法
四、算法设计题
1. 设计在顺序有序表中实现二分查找的算法。
structrecord {int key; int others;};
intbisearch(struct record r[ ], int k)
{
int low=0,mid,high=n-1;
while(low<=high)
{
mid=(low+high)/2;
if(r[mid].key==k) return(mid+1); elseif(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 != nullptr) {
traverseInOrder(bt->left);
if (minNum > bt->key) {
flag = 0;
}
minNum = bt->key;
traverseInOrder(bt->right);
}
}
3. 在链式存储结构上设计直接插入排序算法
voidstraightinsertsort(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;}
}
}