下载文档原格式
华东理工大学网络学院（专科）《数据结构》------ch7图、ch9排序班级学号姓名成绩一、填空题（每空1分，共10分）1.具有n个顶点的有向图最多有n（n-1）条边。
2.在无向图G的邻接矩阵中，求第i个结点的度的方法是求邻接矩阵第i行非零元素之和。
3.堆排序通常采用顺序存储结构。
4. 与快速排序和堆排序相比，归并排序的最大特点是，它是一种稳定的排序方法。
5.具有8个顶点的有向完全图有56 条弧。
6. 在无向图G的邻接矩阵A中，若A[i][j]等于1，则A[j][i]等于 1 。
7.在一个待排序的序列中，只有很少量元素不在自己最终的正确位置上，但离他们的正确位置都不远，则使用直接插入排序方法最好。
8. 已知有向图的邻接矩阵，要计算i号顶点的入度，计算方法是：将i列元素累加。
9. n个顶点的强连通图至少有n 条边，至多有n(n-1) 条边。
二、判断正误（对的用”T”表示，错误的用”F”表示。
每小题1分，共10分）1. ( T )若一个有向图的邻接矩阵中对角线以下元素均为零，则该图的拓扑有序序列必定存在。
2. ( F )快速排序的速度在所有的排序方法中为最快，而且所需附加空间也最少。
3.（ F ）采用邻接表存储的图的深度优先遍历算法类似二叉树的按层次遍历算法。
4.（T ）在待排序的元素序列基本有序的前提下，效率最高的是插入排序。
5.（T ）图的广度优先遍历类似于树的层次遍历。
6.（T ）拓扑排序时，总是在有向图中选择入度为0的顶点输出。
7.（ F ）若要求一个稠密图G的最小生成树，最好用Kruscal算法来求解。
8.（T ）拓扑排序输出的顶点数小于有向图的顶点数，则该图一定存在回路。
9.（T ）设有一稠密图G，则G采用邻接矩阵存储较省空间。
10.（F）n个顶点e条边的图采用邻接矩阵存储，深度优先遍历算法的时间复杂度为O(n+e)。
三、单项选择题（每小题2分，共20分）1.已知图的邻接表如下所示，根据算法，则从顶点0出发按广度优先遍历的结点序列是 C 。
1．顺序存储结构中数据元素之间的逻辑关系是由（存储位置）表示的。
2．若某线性表最常用的操作是存取任一指定序号的元素和在最后进行插入和删除运算，则利用（顺序表）存储方式最节省时间。
3. 执行下面程序段时，语句S的执行次数为(n+1)(n+2)/24 对于线性表最常用的操作是查找指定序号的元素和在末尾插入元素，则选择（顺序表）存储方式最节省时间。
5．在长度为n的顺序表的第i个位置上插入一个元素（1≤ i ≤n+1），元素的移动次数为：n – i + 16．非空的单循环链表由头指针head指示，p 指针指向链尾结点的条件是（p->next==head）。
7．下列选项中，（可以随机访问表中的任意元素）是链表不具有的特点。
8.假设有如下遗产继承规则：丈夫和妻子可以相互继承遗产；子女可以继承父亲或母亲的遗产；子女间不能相互继承。
则表示该遗产继承关系的最合适的数据结构应该是（图）。
9．栈和队列的共同点是（只允许在端点处插入和删除元素）10．一个队列的入队序列是a,b,c,d，则该队列的出队序列是（a,b,c,d）。
11.带头结点的单链表h为空的判断条件是（h->next== NULL）。
12. 下面关于串的叙述中，哪一个是不正确的？（空串是由空格构成的串）13．判断一个最大容量为m的循环队列Q为空的条件是（Q->front==Q->rear）。
14．在一棵树中，每个节点最多有（1）前驱节点？15．已知完全二叉树的第7层有10个叶子结点，则整个二叉树中结点数为（73）。
16. 下面的说法中，不正确的是（稀疏矩阵中大量值为零的元素分布有规律，因此可以采用三元组表方法存储）17．在一棵深度为k的满二叉树中，结点总数为（2k-1）18．数组A中，每个元素的长度为3个字节，行下标从1到5，列下标从1到6，从首地址SA开始连续存放在存储器内，存放该数组至少需要的字节数是（90）。
19. 如果从无向图的任一顶点出发进行一次深度优先搜索即可访问所有的顶点，则该图一定是（连通图）。
《数据结构》练习题一、解答题（共50分）1、（8分）假设用于通讯的电文字符集及其出现的频率如下表所示。
请为这8个字符设计哈夫曼编码，并画出其哈夫曼树，计算WPL 。
2. （8分）若一棵二叉树中序遍历和后序遍历序列分别为：DBEHGAFIC 和DHGEBIFCA 。
试画出这棵二叉树，并写出其先序遍历和层序遍历序列。
3.（16分）以下无向网络以邻接表为存储结构（假设邻接表的顶点表按字母a 、b 、c 、d 、e 、f 、g 、h 的顺序依次存储，邻接表的边表结点按顶点的下标由小到大链接）。
请画出其邻接表，并写出从顶点f 出发，分别进行深度和广度优先遍历的序列，写出用Prime 方法从顶点c开始产生最小生成树的边的序列。
4.（8分）已知键值序列为(44，39，67，25， 52，59，43，84，54，58，15，26，12，73，92，69)，取填充因子α=0.8，采用线性探查法处理冲突，试构造散列表。
⒌（5分）已知一组记录为(67,88,15,12,60,37,7,31,45,81)，用希尔排序方法进行排序，d1=5,d2=3,d3=1,则第二趟的排序结果是（ ）。
⒍（5分）已知一组记录为(67,88,15,12,60,37,7,31,45,81) ，用堆（大根堆）排序方法进行排序，第一趟的排序结果是（ ）。
二、完善程序（共20分，每空2分）1.假设一组递减有序的原始数据存储在数组r 中，存放元素的下标下限为low,下标上字符 出现频率 a 0.05 b 0.03 c 0.24 d 0.16 e 0.08 f 0.24 g 0.18 h0.02限为high,以下是在数组中查找数值为k的折半查找算法。
请填空完善程序。
int BinSearch(int r[ ], int low,int high,int k){ int l,h,m;l= low; h= high;while ( ⑴){m= ⑵;if (k < r[m]) ⑶;else if (k > r[m]) ⑷;else return m;}return 0;}2. 以下程序功能是将数组r中，从下标first到end之间的元素进行快速排序的分区。
数据结构练习题1一、单项选择题，在括号内填写所选择的标号（每小题1分，共12分）2. 以下说法错误的是（）。
A. 抽象数据类型具有封装性。
B. 抽象数据类型具有信息隐蔽性。
C. 使用抽象数据类型的用户可以自己定义对抽象数据类型中数据的各种操作。
D. 抽象数据类型的一个特点是使用与实现分离。
3. 设有一个n n的对称矩阵A，将其上三角部分按行存放在一个一维数组B中，A[0][0]存放于B[0]中，那么第i行的对角元素A[i][i]存放于B中（）处。
A. (i+3)*i/2B. (i+1)*i/2C. (2n-i+1)*i/2D. (2n-i-1)*i/24. 已知单链表A长度为m，单链表B长度为n，若将B联接在A的末尾，其时间复杂度应为（）。
A. O(1)B. O(m)C. O(n)D. O(m+n)5. 假定一个链式队列的队头和队尾指针分别为front和rear，则判断队空的条件为( )。
A. front == rearB. front != NULLC. rear != NULLD. front == NULL7. 在一棵高度为h(假定树根结点的层号为0)的完全二叉树中，所含结点个数不小于( )。
A. 2h-1B. 2h+1C. 2h-1D. 2h8. 一棵树的广义表表示为a(b,c(e,f(g)),d)，当用左子女-右兄弟链表表示时，右指针域非空的结点个数为( )。
A 1B 2C 3D 49. 向具有n个结点的、结构均衡的二叉搜索树中插入一个元素的时间复杂度大致为( )。
A. O(1)B. O(log2n )C. O(n)D. O(nlog2n)10. 具有n个顶点的有向无环图最多可包含( )条有向边。
A．n-1 B．n C．n(n-1)/2 D．n(n-1)11. 图的广度优先搜索类似于树的（）次序遍历。
A. 先根B. 中根C. 后根D. 层次12. 如果将所有中国人按照生日（不考虑年份，只考虑月、日）来排序，那么使用下列排序算法中( )算法最快。
数据结构练习题（一）一、单选题1.栈和队列的共同特点是( )。
A.只允许在端点处插入和删除元素B.都是先进后出C.都是先进先出D.没有共同点2.用链接方式存储的队列，在进行插入运算时( )。
A. 仅修改头指针B. 头、尾指针都要修改C. 仅修改尾指针D.头、尾指针可能都要修改3.?4.以下数据结构中( )是非线性结构。
A. 队列B. 栈C. 线性表D. 二叉树5.设有一个二维数组A[m][n]，假设A[0][0]存放位置在644(10)，A[2][2]存放位置在676(10)，每个元素占一个空间，问A[3][3](10)存放在（）位置。
脚注(10)表示用10进制表示。
A．688 B．678 C．692 D．6966.树最适合用来表示( )。
A.有序数据元素B.无序数据元素C.元素之间具有分支层次关系的数据D.元素之间无联系的数据7.二叉树的第k层的结点数最多为( )。
A．2k-1 +1 D. 2k-18.若有18个元素的有序表存放在一维数组A[19]中，第一个元素放A[1]中，现进行二分查找，则查找A［3］的比较序列的下标依次为( )。
<A. 1，2，3B. 9，5，2，3C. 9，5，3D. 9，4，2，39.对于线性表（7，34，55，25，64，46，20，10）进行散列存储时，若选用H（K）=K %9作为散列函数，则散列地址为1的元素有（）个。
A．1 B．2 C．3 D．410.设有6个结点的无向图，该图至少应有( )条边才能确保是一个连通图。
二、填空题1.通常从四个方面评价算法的质量：_________、_________、_________和_________。
2.一个算法的时间复杂度为(n3+n2log2n+14n)/n2，其数量级表示为________。
3.假定一棵树的广义表表示为A（C，D（E，F，G），H（I，J）），则树中所含的结点数为__________个，树的深度为___________，树的度为_________。
《数据结构（C语言版第2版）》（严蔚敏著）第四章练习题答案第4章串、数组和广义表1．选择题（1）串是一种特殊的线性表，其特殊性体现在（）。
A．可以顺序存储B．数据元素是一个字符C．可以链式存储D．数据元素可以是多个字符若答案：B（2）串下面关于串的的叙述中，（）是不正确的？A．串是字符的有限序列B．空串是由空格构成的串C．模式匹配是串的一种重要运算D．串既可以采用顺序存储，也可以采用链式存储答案：B解释：空格常常是串的字符集合中的一个元素，有一个或多个空格组成的串成为空格串，零个字符的串成为空串，其长度为零。
（3）串“ababaaababaa”的next数组为（）。
A．012345678999 B．012121111212 C．011234223456 D．0123012322345答案：C（4）串“ababaabab”的nextval为（）。
A．010104101B．010102101 C．010100011 D．010101011答案：A（5）串的长度是指（）。
A．串中所含不同字母的个数B．串中所含字符的个数C．串中所含不同字符的个数D．串中所含非空格字符的个数答案：B解释：串中字符的数目称为串的长度。
（6）假设以行序为主序存储二维数组A=array[1..100,1..100]，设每个数据元素占2个存储单元，基地址为10，则LOC[5,5]=（）。
A．808 B．818 C．1010 D．1020答案：B解释：以行序为主，则LOC[5,5]=[（5-1）*100+（5-1）]*2+10=818。
（7）设有数组A[i,j]，数组的每个元素长度为3字节，i的值为1到8，j的值为1到10，数组从内存首地址BA开始顺序存放，当用以列为主存放时，元素A[5,8]的存储首地址为（）。
A．BA+141 B．BA+180 C．BA+222 D．BA+225答案：B解释：以列序为主，则LOC[5,8]=[（8-1）*8+（5-1）]*3+BA=BA+180。
●判断题（一）1.数据元素是数据最小单位。
错2.数据对象就是一组数据元素的集合。
错3.任何数据结构都具备三个基本运算：插入、删除和查找。
错4.数据对象是由有限个类型相同的数据元素构成的。
对5.数据的逻辑结构与各数据元素在计算机中如何存储有关。
错6.如果数据元素值发生改变，则数据的逻辑结构也随之改变。
错7.逻辑结构相同的数据，可以采用多种不同的存储方法。
对8.逻辑结构不相同的数据，必须采用不同的存储方法来储存。
错9.数据的逻辑结构是指数据元素的各数据项之间的逻辑关系。
错●判断题（二）1.顺序存储方式只能用于存储线性结构。
错2.数据元素是数据最小的单位。
错3.数据结构是带有结构的数据元素的集合。
对4.数据的逻辑结构是指各数据元素之间的逻辑关系。
对5.数据结构、数据元素、数据项在计算机中的表示分别称为存储结构、节点和数据域。
对6.数据的物理结构是指数据在计算机内的实际的存储形式。
对●判断题一1.分配给单链表的内存单元地址必须是连续的。
错2.与顺序表相比，在链表中顺序访问所有节点，其算法的效率比较低。
错3.从长度为n的顺序表中删除任何一个元素，时间复杂度都是O（n）。
错4.向顺序表中插入一个元素，平均要移动大约一半的元素。
对5.凡是为空的单链表都是不含任何节点的。
错6.如果单链表带有头结点，则插入操作永远不会改变头节点指针的值。
对7.在循环单链表中，任何一个节点的指针域都不可能为空。
对●判断题二1.顺序存储方式的特点是存储密度大且插入、删除运算效率高。
错2.线性表的顺序存储结构优于链式存储结构。
错3.顺序存储结构属于静态结构而链式存储结构属于动态结构。
对4.由于顺序存储结构要求连续的存储区域，所以再存储管理上不够灵活。
对5.对于单链表来说，只有从头节点开始才能扫描表中全部节点。
对6.对于循环单链表来说，从表中任一节点出发都能扫描整个链表。
对7.双链表的特点是很容易找任一节点的前驱和后继。
对第三章1.栈底元素是不能删除的元素。
栈和队列习题4．1 判断题(在你认为正确的题后的括号中打√，否则打X)。
(1)堆栈和队列都是特殊的线性表。
(√)(2)堆栈和队列都将插入和删除操作限制在表的端点处进行。
( √)(3)只允许在表的一端进行插入和删除操作的线性表称为堆栈。
( √)(4)没有元素的堆栈称为空栈，空栈用不着栈顶指针。
(X )(5)只要堆栈不空，就能任意删除堆栈的元素。
(X )(6)堆栈允许删除的一端称为栈顶，而栈底元素是不能删除的。
( X )(7)n个元素进栈的顺序一定与它们出栈的顺序相反。
( X )(8)对采用链式存储结构的堆栈进行操作不必判断溢出。
(X )(9)给出顺序堆栈的栈顶元素位置的指针是一个指针类型的变量。
( X )(10)判断顺序堆栈是否为空的标志是top是否等于0(top为栈顶指针)。
(√)(11)插入和删除操作比较简单是链接堆栈和链接队列的优点之一。
(√)(12)n个元素进队的顺序与它们出队的顺序一定是相同的。
( √)(13)没有任何元素的队列称为空队。
空队用不着队头指针与队尾指针。
( X )(14)元素进出队列一定满足“先进先出”的规律。
( √)(15)链接队列不存在溢出问题。
( X )(16)在链接队列中删除一个元素是在链表的最前端进行的。
(√)(17)采用循环链表作为存储结构的队列称为循环队列。
(√)(18)堆栈和队列都可以用来解决递归问题。
(X )(19)堆栈和队列都不适合采用散列存储方法。
( √)(20)无论是顺序队列还是链接队列，插入、删除操作的时间复杂度都是O(1)。
( √)4．2单项选择题。
A(1)堆栈和队列的共同之处在于它们具有相同的——。
A．逻辑特性B．物理特性C．运算方法D．元素类型C(2)堆栈和队列都是特殊的线性表，其特殊性在于_______。
A．它们具有一般线性表所没有的逻辑特性B．它们的存储结构比较特殊C．对它们的使用方法做了限制D．它们比一般线性表更简单D(3)若5个元素的出栈序列为1，2，3，4，5，则进栈序列可能是——。
A．2，4，3，1，5 B．2，3，1，5，4 C．3，1，4，2，5 D．3，1，2，5，4 A(4)某队列初始为空，若它的输入序列为a，b，c，d，它的输出序列应为——。
A．a，b，c，d B．d，c，b，a C．a，c，b，d D．d，a，c，b找公式(5)当4个元素的进栈序列给定以后，由这4个元素组成的可能的出栈序列应该有——。
A．24种B．17种C．16种D．14种*(6)设n个元素的进栈序列为1，2，3，…，n，出栈序列为p1，p2，p3，…，pn，若Pi=n，则B(1≤i<n)的值——。
A．为i B．为n-i C．为n-i+l D．有多种可能A(7)设n个元素的进栈序列为p1，p2，p3，…，pn，出栈序列为1，2，3，…，n，若Pn=l，则n(1≤i< n)的值——。
A．为i B．为n-i C．为n-i+l D．有多种可能D(8)若堆栈采用顺序存储结构，正常情况下，往堆栈中插入一个元素，栈顶指针top的变化是______.A．不变B．top=0 C．top-- D．top++C(9)若堆栈采用顺序存储结构，正常情况下，删除堆栈中一个元素，栈顶指针top的变化是______.A．不变B．top=0 C．top-- D．top++B(10)若队列采用顺序存储结构，元素的排列顺序——。
A．与元素的值的大小有关B．由元素进入队列的先后顺序决定C．与队头指针和队尾指针的取值有关D.与作为顺序存储结构的数组的大小有关C(11)“链接队列”这一概念不涉及——。
A．数据的存储结构B．数据的逻辑结构C.对数据进行的操作D．链表的种类C(12)若堆栈采用链式存储结构，栈顶指针为top，向堆栈插入一个由p所指的新结点的过程是依次执行：——，top=p。
A．p=top B．top=p C．p->link=top D．top->link=pB(13)若非空堆栈采用链式存储结构，栈顶指针为top，删除堆栈的一个元素的过程是依次执行：p=top，——，free(p)。
A．top=p B．top=p->link C．p=top->link D．p=p->linkC(14)若队列采用链式存储结构，队头元素指针与队尾元素指针分别为front和rear，向队列中插入一个由p所指的新结点的过程是依次执行：——，rear=p。
A．rear=p B．front=p C．rear->link=p D．front->link=pD(15)若非空队列采用链式存储结构，队头元素指针与队尾元素指针分别为front和rear，删除队列的一个元素的过程是依次执行：p=front，——，free(p)。
A．rear=p B．rear=p->link C．rear=p->link D．front=p->linkC(16)在循环队列中，若front与rear分别表示队头元素和队尾元素的位置，则判断循环队列队空的条件是——。
A．front=rear+1 B。
rear=front+1 C．front--rear D．b叭t：0A (17)若描述某循环队列的数组为ClUELIE[M]，当循环队列满时，队列中有——个元素。
A．M B．M-1 C．M十1 D．M+2D (18)在解决计算机主机与打印机之间速度不匹配问题时通常设置一个打印数据缓冲区，主机将要输出的数据依次写入该缓冲区，而打印机则依次从该缓冲区中取出数据打印，该缓冲区应该是一个——结构。
A．线性表B．数组C．堆栈D．队列C(19)设计一个递归问题的非递归算法通常需要设置——结构。
A．线性表B．数组C．堆栈D．队列*(20)中缀表达式A-(B+C／D)*E的后缀形式是——。
A．ABC+D／*E—B．ABCD／+E*—C．AB-C十D／E* D．ABC-+D／E* 4．3 填空题。
(1)堆栈和队列的逻辑结构都是线性结构。
(2)堆栈的插入和删除操作都是在栈顶位置进行，而队列的插入操作在队尾进行，删除操作在队头进行。
(3)对某堆栈执行删除操作时，只有在栈顶情况下，才会将栈底元素删除。
(4)在具体的程序设计过程中，堆栈的顺序存储结构一般是利用一个数组描述的，同时还要定义一个整型变量来栈顶。
(5)若堆栈采用顺序存储结构，在不产生溢出的情况下往堆栈中插人一个新元素，首先移动，然后写入。
(6)若队列采用顺序存储结构，未溢出时插入一个元素首先插入一个元素，然后再写入。
(7)当堆栈的最大长度难以估计时，堆栈最好采用链式存储结构。
(8)递归算法都可以通过设置堆栈机制改写成等价的非递归算法。
*(9)中缀形式的算术表达式A+(B-C)／D*E的后缀形式为——。
*(10)后缀形式的算术表达式ABCD/-E*+的中缀形式为——。
4．4 已知堆栈采用链式存储结构，初始时为空，请画出a，b，c，d四个元素依次进栈以后该堆栈的状态，然后再画出此时的那个栈顶元素出栈后堆栈的状态。
4．5 若按从左到右的顺序依次读人已知序列{a，b，c，d，e，f，g1中的元素，然后结合堆栈操作，能得到下列序列中的哪些序列(每个元素进栈一次，下列序列表示出栈的次序)?{d，e，c，f，b，g，a} {f，e，g，d，a，c，b}{e，f，d，g，b，c，a} {c，d，b，e，f，a，g}4．6 设有编号1，2，3，4的四辆列车，顺序进入一个栈式结构的站台，请写出这四辆列车开出车站的所有可能的顺序。
4．7 设STACK[M]为n(n>2)个堆栈共享。
各栈栈顶指针为top[n]，分别指出各栈栈顶元素的位置；栈底指针为bot[n+1]，分别指出各栈栈底元素的位置。
初始时，bop[i]=bot[i]=i*ROUND(M／n—0．5) (i=1，2，....，n)其中，ROUND()为四舍五人取整函数。
请写一算法，该算法向任意指定的第i个堆栈插入一个新的元素x。
仅当M个空间全部占用时才产生溢出，并报告相应信息(1≤i≤n)。
4．8 设中缀表达式E存放于字符数组中，并以@作为结束标志。
请写出判断一个中缀表达式E中左、右圆括号是否配对的算法。
4．9 写出将中缀表达#(a+b)／c-d#变换为后缀表达式的过程中，每读到一个单词时堆栈的状态(#为中缀表达式的左、右分界符)。
4．10 已知n为大于等于零的整数，请写出利用堆栈计算下列递归函数f(n)的非递归算法。
4．11 已知Ackerman函数定义如下：(1)写出递归算法；(2)利用堆栈写出非递归算法；(3)根据非递归算法，求出A(：K(2，1)的值。
4．12 已知求两个正整数m和n的最大公约数的过程可以表达为如下递归函数：请写出求解该递归函数的非递归算法。
m MOD n表示m对n取模。
4．13 假设以数组Q[M]存放循环队列的元素，同时设置变量rear与qlen分别指示循环队列中队尾元素的位置和队列中元素的个数。
请给出此循环队列的队满条件，并写出相应的进队与出队算法(在出队算法中要求返回队头元素)。
4．14 编写一非递归算法，对于给定的十进制整数n，打印出对应的r进制整数(2≤r≤16，r<>10)。
4．15 梵塔问题是这样的：一个底盘上有三根竖着的针，初始时A针穿着一叠盘片(如图4，20所示)，现要求将这一叠盘片移到C针上，并且任何时刻不得将大盘放在小盘之上，而且每一次只允许移动一张盘片。
写一算法，打印出正确的操作步骤。
提示：将n张盘片由A依次移到C，B作为辅助针。
当n=1时，可以直接完成。
否则，将顶上的n—1张盘片移到B针上，用C针作为辅助针；然后移第n张盘片，最后将B上的n—1张盘片移到C针上，并用A针作为辅助针。
栈和队列历年试题1．栈和队列都是（）A．限制存取位置的线性结构B．顺序存储的线性结构C．链式存储的线性结构D．限制存取位置的非线性结构2．若数组s[0..n-1]为两个栈s1和s2的共用存储空间，且仅当s[0..n-1]全满时，各栈才不能进行进栈操作，则为这两个栈分配空间的最佳方案是：s1和s2的栈顶指针的初值分别为（）A．1和n+1 B．1和n/2 C．－1和n D．－1和n+13.若进栈序列为a,b,c，则通过入出栈操作可能得到的a,b,c的不同排列个数为( )A.4B.5C.6D.74．假设元素只能按a,b,c,d的顺序依次进栈，且得到的出栈序列中的第一个元素为c，则可能得到的出栈序列为________________，不可能得到的出栈序列为________________。
5．在栈的顺序实现中，若栈不满，则进栈操作可以用下列算法片断实现：_____________；sq -> data[sq -> top]=x；6．链队列实际上是一个同时带有头指针和尾指针的单链表，尾指针指向该单链表的_____________。
