数据结构期末考试题及练习题
2009-06-25 16:20阅读：
一、 单选题
1. 计算机算法指的是（ b ）。
A．程序
B．问题求解步骤的描述
C．调度方法
D．排序方法
2. 以下数据结构中，（a ）个是非线性数据结构。
A．树
B．字符串 C．队
D．栈
3. 对于顺序存储的线性表，访问元素和插入元素的时间复杂度分别为：（ c ）。
A．O(n) O(n)
B．O(n) O(1)
C．O(1) O(n)
D．O(1) O(1)
4. 在单链表指针为p的结点之后插入指针为s的结点，正确的操作是（ b ）。
A.p->next=s;s->next=p->next
B.s->next=p->next; p->next=s
C.p->next=s;p->next=s->next
D.p->next=s->next; p->next=s
5. n个顶点
的有向图中,含有向边的数目最多为( d )
A．n-1
B．n
C．n(n-1)/2
D．n(n-1)
6. 循环队列存储在数组A[0..m]中，则入队时的操作为（ d ）
A．rear=rear+1
B．rear=(rear+1)mod(m-1)
C． rear=(rear+1)mod m
D． rear=(rear+1)mod(m+1)
7. 字符串’ababaabab’的next函数为（ d ）
A.011232232 B.012341234
C.011122334 D.
011234234
8. 若一棵二叉树具有10个度为2的结点，5个度为1的结点，则度为0的结点个数为（ b
）
A．9 B．11
C．15
D．不确定
9.
设有数组A[i,j]，数组的每个元素长度为3字节，i的值为1到8，j的值为1到10，数组从内存首地址BA开始顺序存放，当
以列为主序存放时，元素 A[5,8]的首地址为（ b ）。
A．BA+141 B．BA+180
C．BA+222
D．BA+225
10. n个顶点的带权无向连通图的最小生成树包含(b )个顶点
A．n-1
B．n
C．n/2
D．n+1
11．有关二叉树的下列说法正确的是（ b ）
A．二叉树的度为2
B．一棵二叉树的度可以小于2
C．二叉树中至少有一个结点的度为2 D．二叉树中任何一个结点的度都为2
12．关键路径是AOE网中（ a ）。
A．从源点到汇点的最长路径
B．从源点到汇点的最短路径
C．最长回路
D．最短路径（从源点到汇点的所有路径中，经过弧的数目最多的路径）
13．若查找每个记录的概率相等，则在具有n个记录的连续文件中采用顺序查找查找一个记录，其平均查找长度ASL为（
c
）。
A．(n-1)/2
B．n/2
C．(n+1)/2
D．n
14．就平均性能而言，目前最好的内部排序方法是（d ）
A．冒泡排序 B．希尔排序
C．堆排序 D．快速排序
15．已知广义表LS=((a,b,c),(d,e,f))，运用head和tail函数取出LS中原子e的运算是（ d
）
A．head(tail(LS))
B．tail (head (LS)
C．head(tail(head(tail(LS)))) D．head(tail(tail (head
(LS))))
17．在n个结点的顺序表中，算法的时间复杂度是O（1）的操作是：( a )
A. 访问第i个结点（1≤i≤n）和求第i个结点的直接前驱（2≤i≤n）
B. 在第i个结点后插入一个新结点（1≤i≤n）
C. 删除第i个结点（1≤i≤n）
D. 将n个结点从小到大排序
18．在单链表指针为p的结点之后插入指针为s的结点，正确的操作是：（ b ）。
A．p->next=s;s->next=p->next; B．
s->next=p->next;p->next=s;
C．p->next=s;p->next=s->next; D．
p->next=s->next;p->next=s;
19. 设栈的输入序列是1，2，3，4,则（d ）不可能是其出栈序列。
A. 1，2，4，3，
B. 2，1，3，4，
C. 1，4，3，2，
D. 4，3，1，2，
E. 3，2，1，4，
20. 循环队列存储在数组A[0..m]中，则入队时的操作为（ d ）。
A. rear=rear+1
B.
rear=(rear+1) mod (m-1)
C. rear=(rear+1) mod m
D. rear=(rear+1) mod (m+1)
21. 若已知一个栈的入栈序列是1, 2, 3, …, n，其输出序列为p1, p2，p3，…，pn，
若p1=n，则pi为 ( c )
A．i
B．n=i C．n-i+1
D．不确定
22．串 ‘ababaaababaa’ 的next的函数值为（ c ）。
A．012345678999
B．012121111212
C．011234223456
D．0123012322345
23．若一棵二叉树具有10个度为2的结点，5个度为1的结点，则度为0的结点个数是（ b ）
A．9 B．11
C．15
D．不确定
24．高度为 k的二叉树最大的结点数为（ c ）。
A．2k B．2k-1
C．2k-1
D．2k-1-1
25．边远山区的N个小村庄，现要为他们建成能互相通信的网，并且总的花费最少，这可以归结为什么问题（ d ）
A最短路径 B关键路径 C拓扑排序
D最小生成树
26．当一个有n个顶点的无向图用邻接矩阵A表示时，顶点Vi的度是（ b ）。
A． B． C．
D． +
30．一组记录的关键码为（46，79，56，38，40，84），则利用快速排序的方法，以第一个记录为基准得到的一次划分结果
为（ a ）。
A．(40,38,46,56,79,84)
B. (40,38,46,79,56,84)
C．(38,40,46,56,79,84)
D. (40,38,46,84,56,79)
31．在双向链表指针p的结点前插入一个指针q的结点操作是（ c ）。
A.
p->Llink=q;q->Rlink=p;p->Llink->Rlink=q;q->Llink=q；
B.
p->Llink=q;p->Llink->Rlink=q;q->Rlink=p;q->Llink=p->Llink;
C.
q->Rlink=p;q->Llink=p->Llink;p->Llink->Rlink=q;p->Llink=q;
D.
q->Llink=p->Llink;q->Rlink=q;p->Llink=q;p->Llink=q;
33.在解决计算机主机与打印机之间速度不匹配的问题时，通常设置一个打印数据缓冲区，主机将要打印的数据依次写入缓
冲区，而打印机则依次驱除数据打印，该缓冲区该是一个什么结构（d ）
A 堆栈 B 图
C 树
D 队列
35．串的长度是指（ b ）。
A．串中所含不同字母的个数
B．串中所含字符的个数
C．串中所含不同字符的个数
D．串中所含非空格字符的个数
36．具有10个叶子结点的二叉树中有（b ）个度为2的结点。
A．8
B．9
C．10
D．ll
37. 有关二叉树下列说法正确的是（ b ）。
A．二叉树的度为2
B．一棵二叉树的度可以小于2
C．二叉树中至少有一个结点的度为2 D．二叉树中任何一个结点的度都为2
38．一个n个顶点的连通无向图，其边的个数至少为（ a ）。
A．n-1
B．n
C．n+1
D．nlog2n
39．下列关于AOE网的叙述中，不正确的是（ b ）。
A．关键活动不按期完成就会影响整个工程的完成时间。
B．任何一个关键活动提前完成，那么整个工程将会提前完成。
C．所有的关键活动提前完成，那么整个工程将会提前完成。
D．某些关键活动提前完成，那么整个工程将会提前完成。
40. 已知广义表L=（（x,y,z），a，（u，t，w）），从L表中取出原子项t的运算是（d
）。
A. head（tail（tail（L）））
B. tail（head（head（tail（L））））
C. head（tail（head（tail（L）））） D. head(tail((tail(tail(L））））)
41．适用于折半查找的表的存储方式及元素排列要求为( d )
A．链接方式存储，元素无序
B．链接方式存储，元素有序
C．顺序方式存储，元素无序 D．顺序方式存储，元素有序
42.若查找每个记录的概率均等，则在具有n个记录的连续顺序文件中采用顺序查找法查找一个记录，其平均查找长度ASL为(
c )。
A． (n-1)/2 B. n/2
C. (n+1)/2
D. n
43．下列四个序列中，哪一个是堆（ c ）。
A. 75,65,30,15,25,45,20,10 B.
75,65,45,10,30,25,20,15
C. 75,45,65,30,15,25,20,10 D.
75,45,65,10,25,30,20,15
44．已知某二叉树的后序遍历序列是dabec, 中序遍历序列是debac , 它的前序遍历是（d
）。
A．acbed
B．decab
C．deabc D．cedba
二、填空题
1. 带头结点的单循环链表L中只有一个元素结点的条件是 l->next->next=null
。
2. 串中所含字符个数称为该串的_______长度 ________。
3. 深度为h的完全二叉树至少有 2^(k-1)
个结点，至多有 2^k-1
个结点。
4. 对关键字序列(52，80，63，44，48，91)进行一趟快速排序之后得到的结果为 48 44
52 63 80 91 。
5．完全二叉树中，结点个数为n，则编号最大的非终端结点的编号为__n/2_向下取整
___。
7. 设一棵完全二叉树具有1000个结点，则此完全二叉树有 500 个叶子结点，有 499
个度为2的结点，有 1 个结点只
有非空左子树，有 0 个结点只有非空右子树。
8．在堆排序和快速排序中，若初始记录接近正序或反序，则选用 堆排序
；若初始记录基本无序，则最好选用
快速排序 。
9. 在n个结点的单链表中要删除已知结点*p，需找到它的 前驱
，其时间复杂度为 o(n)
。
10．模式串P=‘abaabcac’的next函数值序列为_01122312___
____。
11．一棵左右子树不空的二叉树在先序线索化后，其空指针域数为: 1
。
12．对有18个元素的有序表A[1，18]做折半查找，则查找A[3]的比较序列的下标依次为
_ ___ _。
三、判断题：对打“√” ；错打“×”，并说明理由。
1. 数据元素是数据的最小单位。( 2 )
2. 顺序存储结构的主要缺点是不利于插入或删除操作。( 1 )
3. 线性表的长度是线性表所占用的存储空间的大小。( 2 )
4. 队列是一种插入与删除操作分别在表的两端进行的线性表，是一种先进后出型结构。（ 2
）
5. 完全二叉树中，若一个结点没有左孩子，则它必是树叶。( 1 )
6. 哈夫曼树是带权路径长度最短的树，路径上权值较大的结点离根较近。( 1 )
7. 折半查找与二叉排序树的时间性能有时不相同。（
）
8. 十字链表是无向图的一种存储结构，而邻接多重表是有向图的一种存储结构。（ 2
）
9. 在用堆排序算法排序时，如果要使排序后的记录序列按关键字非递减有序排列，则需要采用“大根堆”。（ 1
）
10. 强连通分量是无向图的极大强连通子图。（ 2 ）
11. 散列表的装填因子α越小，发生冲突的可能性就越小。（ 1 ）
三．算法设计题
1、 假设以带头结点的单循环链表表示队列，其中结点结构为（data，next），并且只设一个指针rear指向队尾结点，但不
设头指针，请写出相应的入队：EnQueue(Li nkList &rear,ElemType x)和出队 DeQueue(Li
nkList &rear,ElemType &x)算
法。
2．是利用栈和队列实现对一个字符串的逆置。
3．已知Q是一个非空队列，S是一个空栈。仅用如下给定的队列和栈的ADT函数和尽量少的工作变量，使用C或C++语言编写一
个算法，将队列Q中的所有元素逆置。
l 栈的ADT函数有：
void MakeEmpty(Stack &S) 置空栈
bool Push(Stack &S,DataType e)
新元素e进栈，入栈成功返回TRUE，否则返回FALSE
DataType Pop(Stack &S ) 出栈，返回栈顶值,否则返回空值
bool isSEmpty(Stack S)
判栈空否,若空返回TRUE，否则返回FALSE
l 队列的ADT函数有：
bool EnQueue(Queue &Q, DataType e)
元素e进队，入队成功返回TRUE，否则返回FALSE
DataType DeQueue(Queue &Q) 出队列，若队列非空返回队头值,
否则返回空值
bool isQEmpty( Queue Q ) .
判队列空否。若空返回TRUE，否则返回FALSE
4．下面的算法在中序线索二叉树中求结点p的中序后继，试补充完整（线索树的结点有五个域data,lchild,rchild,左、右
标志域ltag、rtag，并规定标志0指向孩子，1指向线索）。
Status InorderNext(BiThrNode *p)//返回p结点的中序后继结点
{
if (__ _①_______)
return p->rchild；
else {
p = p->rchild;
while (___②________)
_______③___________；
return p;
}
}
四．将如下所示的有向图给出其存储结构的邻接链表表示（注：这里顶点的邻接点按降序排列），然后分别写出对其邻接表
从顶点1开始进行深度优先遍历序列和广度优先遍历序列的结果。（画出邻接链表4分，求出深度优先序列和广度优先序列各
3分，共10分）
五、已知一棵二叉树的前序遍历的结果是ABDFCEGH，中序遍历的结果是BFDAGEHC，
（1）画出这棵二叉树；要求写出具体步骤。
（2）画出这颗二叉树的后序线索树；
（3）将这颗二叉树转换成对应的树（或森林）。
六、已知一棵二叉树的中序遍历的结果是DCBGEAHFIJK，后序遍历的结果是DCEGBFHKIJ，
（1）画出这棵二叉树；要求写出具体步骤。
（2）画出这颗二叉树的前序线索树；
（3）将这颗二叉树转换成对应的树（或森林）。
七、假定用于通信的电文仅由8个字母c1, c2, c3, c4, c5, c6, c7, c8组成,
各字母在电文中出现的频率分别为5, 25, 3,
6, 10, 11, 36,
4。试画出对应的Huffman树（请按照左子树根结点的权值小于等于右子树根结点的权值的次序构造），并
求其 WPL 和 这8个字母的Huffman编码 （按步骤求出Huffman树）。
+
八、给定关键码序列（26，25，20，33，21，24，45，204，42，38，29，31），要用哈希法进行存储，规定装填因子a=0.6
（1）请给出除留余数法的哈希函数；
（2）用线性探测法解决冲突，请画出插入所有的关键码后得到的哈希表；
（3）计算等概率情况下查找成功的平均查找长度。
