河北工程大学数据结构复习题

单项选择题1.数据的（B）包括集合、线性、树和图4种基本类型A．存储结构B．逻辑结构C．基本运算D．算法描述2.对一个长度为n的顺序表，在第i个元素（1≤i≤n+1）之前插入一个新元素时需向右移动（B）个元素。

A．n-i B．n-i+1 C．n-i-1 D．i3下面程序的时间复杂度为（C ）。

For(i=0;i<m;i++)For(j=0;j<n;j++)A[i][j]=i*j;A.O(m2)B. O(n2)C. O(n*m)D.O(n+m)4长度为n的线性表采用顺序存储结构，在其第i个位置插入一个新元素的算法时间复杂度为（C）。

若没说明在第几个位置插入，则其复杂度为DA．O(0) B．O(1) C．O(n) D．O(n2) 5.数据结构就是研究（D ）。

A．数据的逻辑结构B．数据的存储结构C．数据的逻辑结构和存储结构D．数据的逻辑结构、存储结构及其数据在运算上的实现6下面关于算法的说法，错误的是（D）。

A．算法最终必须由计算机程序实现B．为解决某问题的算法和为该问题编写的程序含义是相同的C．算法的可行性是指指令不能有二义性D．以上三种说法都错误7线性表L=（a1，a2 ，……an，）下列说法正确的是（D ）。

A．每个元素都有一个直接前驱和一个直接后继B．线性表中至少要有一个元素C．表中所有元素的排列顺序必须是由小到大或由大到小D．除第一个和最后一个元素外，其余每个元素都有且仅有一个直接前驱和一个直接后继8．下面关于线性表叙述错误的是（ B ）。

A．线性表采用顺序存储，必须占用一段地址连续的单元B．线性表采用顺序存储，便于进行插入和删除操作C．线性表采用链式存储，不必占用一段地址连续的单元D．线性表采用链式存储，便于进行插入和删除操作9用链表表示线性表的优点是（C）A．便于随机存取B．存储空间比顺序存储方式少C．便于插入和删除D．数据元素的存储顺序与逻辑顺序相同10若某线性表中最常用的操作是取第i 个元素和找第i个元素的前趋元素，则采用（ D ）存储方式最节省时间。

A．单链表B．双链表C．单向循环D．顺序表11.若队列采用顺序存储结构，元素的排列顺序（B）A．与元素值的大小有关B．由元素进入队列的先后顺序决定C．与队头指针和队尾指针的取值有关D．与作为顺序存储结构的数组大小有关12.三个元素按照A,B,C的顺序入栈，下列哪一个是不合法的出栈序列？（B）A. ABCB. CABC. ACBD. BAC13假定一个顺序循环队列存储于长度为n的一维数组中，其队头和队尾指针分别用front 和rear表示，则判断队满的条件是（A）A．（rear+1）%n==front B．front+1==rearC．rear==（front-1）%n D．rear==（front+1）%n14假定一个顺序循环队列的队头和队尾指针分别用front和rear表示，则判队空的条件是（D）。

A．（front+1）%n==rear B．front==rear+1C．front==0 D．front==rear15.深度为5（假设空树的深度为0）的二叉树至多有（C）结点。

A．64 B．32 C．31 D．6316一个具有n个顶点的无向完全图的边数为（ B ）A．n(n+1)/2 B．n(n-1)/2 C．n(n-1) D．n(n+1)17后序遍历序列为G D B E F C A,中序遍历序列为D G B A E C F，则前序遍历序列为（）。

A．A B G D C E F B．A B D G C F E C．B D G C E FA D．A BD G CE F18 如果以链表作为栈的存储结构，则出栈操作时（C）A．必须判别栈是否满B．对栈不作任何判别C．必须判别栈是否空D．判别栈元素的类型19线性表采用链式存储时，其地址（D）。

A．必须连续B．部分地址必须连续C．必须连续D．连续与否均可20数据的（B）包括集合、线性、树和图4种基本类型。

A．存储结构B．逻辑结构C．基本运算D．算法描述21一棵完全二叉树上有15个结点，其深度是不超过（C）的最大整数。

A．2 B．3 C．4 D．A~C项都不对22若某线性表中最常用的操作是在最后一个元素之后插入一个元素和删除最后一个元素，则采用（D）存储方式最节省运算时间。

A．单链表B．双链表C．带头结点的双循环链表D．容量足够大的顺序表23.二叉树中第5层上的结点个数最多为_C___A.8B.15C.16D.3224.深度为5的二叉树至多有（ D ）结点。

A．64 B．32C．31 D．6325.将一棵有100个结点的完全二叉树从上到下，从左到右依次对结点进行编号，根结点的编号为1，则编号为49的结点的左孩子的编号为__A____。

A.98B.99C.50D.4826．已知广义表的表头为A，表尾为(B,C)，则此广义表为___B_____A.（A,(B,C)）B.（A,B,C）C.((A),B,C)D.(( A,B,C))填空题1.对于给定的n个元素，可以构造出的逻辑结构有（集合）、（线性）、（树）、（图）4种。

2数据元素在计算机中的（）方式称为存储结构。

3线性结构中的元素之间存在（一对一）关系，树形结构中元素之间存在（一对多）关系，图形结构中的元素之间存在（多对多）关系。

4设单链表的结点结构为（data，*next），已知指针p指向单链表中X结点，指针q指向y的新结点，若将结点y插入到结点x之后，则需要执行以下两条语句（q->next=p->next），（p->next=q ）。

5数据的（逻辑）结构与数据元素本身的内容和形式无关。

6一个算法的好坏取决于该算法的（时间复杂度）和（空间复杂度）。

7数据结构中评价算法的两个重要指标是（时间复杂度）、空间复杂度。

8一个循环队列存储于下标由0开始且长度为m的一维数组中，假定队头和队尾指针分别为front和rear，则判断队空的条件为（（rear+1）%n==front）。

则判断队满的条件为（front==rear）。

9 队列的插入操作是在队列的（队尾）进行，删除操作是在队列的（队头）进行。

10堆栈的逻辑特点是（先进后出），队列的逻辑特点是（先进先出）。

11堆栈的逻辑特点是（先进后出），队列的逻辑特点是（先进先出）。

二者的共同点是只允许在它们的（端点）处插入和删除数据元素。

12堆栈操作设输入元素的顺序为1,2,3,4,5，要在栈的输出端得到43521，则应进行栈的基本运算表示应为：Push（S,1），Push(S,2)，Push(S,3)，Push(S,4)，Pop(S)，（Pop(S) ），（Push(S,5)），Pop(S)，Pop(S)，Pop(S)。

13设有一个链队，结点结构为data|next，front为队头指针，rear为队尾指针，当执行入队操作时需执行下列语句：malloc(p)；p->data=x; p->next=NULL；（）；（）；13、一棵二叉树有67个结点,这些结点的度要么是0，要么是2。

这棵二叉树中度数为2的结点有个。

14、一个哈夫曼(Huffman)树有19个结点，则其叶结点的个数是。

15、一棵深度为6的满二叉树有31个分支结点和32个叶子。

16、设二叉树结点的先序序列为ABDECFGH，中序序列为DEBAFCHG,则二叉树的后序序列是。

17. 克鲁斯卡尔算法的时间复杂度为（），适合求（）的最小生成树。

18.空串是（），其长度等于（）。

19.空格串是（），其长度等于（）。

20.两个字符串相等的充分必要条件是（）。

21写出模式串p=“abaabcac”的next函数值序列为（）22、设有一稀疏图G，则G采用存储结构较省空间。

23、已知广义表A=((a,b,c),(d,e,f)),则运算head(head (tail（A）)))=___ ________.24．一棵深度为6的满二叉树有个分支结点和个叶子。

25．在对一组记录（54，38，96，23，15，72，60，45，83）进行直接插入排序时，当把第7个记录60插入到有序表时，为寻找插入位置至少需比较次。

应用题1．什么是线性结构？线性结构的特点是什么？列举？2.什么是树形结构？树形结构的特点是什么？3.什么是图结构？4.已知二叉树的前序ABCDEFGHIJ和中序CDBFEAIHGJ，试构造出相应的二叉树。

5.已知一棵二叉树的后序遍历序列为EICBGAHDF，中序遍历序列为ECIFBAGDH，请画出这棵二叉树，7. 对于一个有10000个结点的二叉树，树叶最多有多少个？最少有多少个？8写出某个有向图的顶点V和弧E的邻接矩阵。

9已知某二叉树，写出前序遍历、中序遍历和后序遍历10根据普里姆算法思想，画出构造该无向带权图最小生成树的过程。

（5分）11的有向带权图，根据狄克斯特拉算法思想，画出生成从顶点A到其余各项顶点最短路径的过程。

12已知序列{34，17，6，29，33，11，80，37}请用冒泡排序的方法从大到小进行排序，并给出详细过程。

13已知序列{34，17，6，29，33，11，80，37}请用直接选择排序的方法从大到小进行排序，并给出详细过程。

14、已知一棵二叉树的中序序列和后序序列分别为：DBGEACHF和DGEBHFCA，则该二叉树的前序序列是什么？试画出这棵二叉树。

15、给定权值集合{15,03,14,02,06,09,16,17}，构造相应的哈夫曼树，并计算它的带权路径长度。

16．设一数组A[5][6]，A[0][0]的地址为1100，且每个元素占2个存储单元，则这个二维数组的存储量为多少？A[4][5]的地址为多少？如按行优先顺序存储A[2][3]的地址为多少？17.用序列（46，88，45，39，70，58，101，10，66，34）建立一个排序二叉树，画出该树，并求在等概率情况下查找成功的平均查找长度18.按下列要求，写出相应结果设关键字的输入次序为45，24，53，45，12，24，90。

画出生成的二叉排序树（5分)。

19试画出具有3个结点的二叉树所有不同形态（5分）。

写算法1.请写出顺序存储的线性表中，在第i个位置插入和删除数据元素x的实现算法。

（请在关键部分给出注释。

）2.请写出链式存储的线性表中，在第i个位置插入和删除数据元素x的实现算法。

（请在关键部分给出注释。

）3. 请写出链式堆栈操作中，入栈和出栈的实现算法。

（请在关键部分给出注释。

）。