数据结构题目及答案

1、思考题一、填空题：(20分，每空1分)1、数据的基本单位是数据元素,最小单位是s数据项。2、x=91; n=100;while(n>0)if (x>100) x=x-10; n=n-1;else x=x+1;上述算法中语句 x=x+1 的执行次数T(n尸O(N13)。3、已知二维数组A2111采用行序为主方式存储，每个元素占4个存储单元，并且 A00的存储地址为1016 ,则A105的存储地址4、在进出规则上，队列的特点是,堆栈的特点5、深度为5 (根层次为1)的二叉树最多有 个结点；第4层 最多有个结点。6、在长度为n的顺序表(即顺序存储结构的线性表)中插入一个元素， 需要平均移

2、动个元素。7、在无向图中，若对于任意一对顶点 vi和vj,都存在,则称此图 是连通图。8、设有一个10阶的对称矩阵A,采用压缩存储方式，以行为主存储， a00 为第一个元素，其存储地址为 1,每个元素占1个地址空间，则a75的地 址为。9、线性表的两种常用存储结构有 存储结构和 存储结构。10、当增量d为1时，该趟希尔排序与排序基本一致。 11、数据结构是研究数据的 ,和算法。12、常用图的存储结构有：邻接矩阵, 邻接表 ，十字链表 ，邻接多重表；13、顺序表的插入算法int Insert(elemtype List,int *num,int i, elemtype x)int j;if(i&

3、lt;0| | i>*num+1)printf( n i 值不合法！”)； return 0;for (j=*num;j>=i;j-);/*数据元素依次后移*/ List i=x;(*num)+;return 1; 1在单链表 中设置头结点 的作用是 简化操作2顺序存储结构使线性表中逻辑上相邻的数据元素在物理位置上也相邻。因此，这种表便于访问，3设输入元素的顺序为1,2,3,4,5,要在栈S的输出端得到43521 ,则应进行栈的基本运算 表示应为：Push(S,1), Push(S,2), Push(S,3), Push(S,4), Pop(S), Pop(S), Pop(S),

4、Pop(S)。4由下标0开始且元素个数为n的一维数组实现循环队列时，为实现下标变量m加1后在该数组的有效下标范围内循环，可采用的表达式是m5对行下标由1到50、列下标由1到80的二维数组a,若该数组的起始地址为2000且 每个元素占2个存储单元，并以行为主序顺序存储，则元素 a4568的存储地址为 ;若以列为主序顺序存储，则元素 a4568的存储地址为6设F是由、T2、T3三棵树组成的森林，与F对应得二叉树为Bo已知Ti、T2、T3的结点数分别为m、2和山，则二叉树B的左子树中有结点，二叉树右子树中有个结点o设n0为哈夫曼树叶子结点的数目，则该哈夫曼树共有个结点。7具有10个顶点的无向图，边的

5、总数最多为 8分块查找中，若索引表对各块内均采用顺序查找，有900个元素的线性表若分成25块， 其平均查找长度为。9若一个待散列存储的线性表长度为 n,用于散列的散列表长度为 m,则装填因子a为10 在堆排序和快速排序中，若初始记录接近正序或反序，则选用，若初始记录无序, 则最好用11从一个无序序列建立一个堆的方法是：首先将待排序的所有关键字分放到一棵 的各个结点中，然后从i=的结点ki开始，逐步把ki-1 ,ki-2,k1为根的子树 排成堆，直到以k1为根的树排成堆，就完成了建堆的过程。12 算法的重要特性有 有穷性 、确定性、可行性、输入和输出。二、单选题：（每题1分，共10分）1、对于一

6、个头结点为head的带头结点的单链表，判定该表为空表的条件（）A. head= =NULL;B. head->next= =NULL;C. head->next= = head;D. head!=NULL2、下述排序算法中，稳定的（）A.直接选择排序 B.直接插入排序 C.快速排序D.堆排序3、具有线性结构的数据结构是（A.树B.图C.栈和队列D.以上都不是4、评价一个算法时间性能的主要标准是()A.算法易于调试B.算法易于理解C.算法的稳定性和正确性D.算法的时间复杂度5、若用冒泡排序对关键字序列18, 16, 14, 12, 10, 8进行从小到大的排序，所需进行的关键字比较总

7、次数是()A. 10B. 15C. 21D. 346、对稀疏矩阵进行压缩是为了(A.便于进行矩阵运算C.节省存储空间7、设以数组 Am存放循环队列的元素和rear,则当前队列中的元素个数为A. (rear -front + m)%m !C. (front - rear + m)%mB.便于输入和输出D.降低运算的时间复杂度，其头指针、尾指针分别为 front)B. rear-front+1D. (rear-front)%m8、已知二叉树如图所示，则其顺序存储结构为(A.B.C.IA I IC IFa I c |f I g D9、在有n个叶子结点的哈夫曼树中，其结点总数为()A.不确定B. 2n

8、C. 2n+1D. 2n-110、一个有n个顶点的无向图最多有()条边。A. nB. n(n-1)C. n(n-1)/2D.2n11.数据的存储结构包括顺序、链接、散列和 4中基本类型。A.向量B.数组C.集合D.索引1 .下面关于线性表叙述中的错误是 ?A.线性表采用顺序存储，必须占用一段地址连续的单元B.线性表采用顺序存储，便于进行插入和删除操作C.线性表采用链式存储，不必占用一段地址连续的单元D.线性表采用链式存储，便于进行插入和删除操作2 .栈和队列都是特殊的线性表，其特殊性在于 A.它们具有一般线性表所没有的逻辑特性B.它们的存储结构比较特殊 D.它们比一般线性表更简单, ,5,列下

9、标j=0,1，10,则该数组含有的元4 .已知一维数组的行卜标i=-3，-2，-1，0，素个数为 A.88B. 99C. 80D. 905 .若对n个元素进行插入排序，则进行第i趟排序之前有序表中的元素个数为 oA. iB. i+1C. i-1D. 16 . 一棵完全二叉树上有1001个结点，其叶子结点的个数是 A. 250B. 500C. 505D. A C 都不对7 .设无向图的顶点个数为n,则该无向图最多有 条边。A. n-1B. nV)C. nV)D. n2228.存放元素的数组下标由1开始，对有18个元素的有序表作二分(折半)查找，则查找A3时比较的下标序列为 A. 1,2,3B.

10、9,5,2,3C. 9,5,3D. 9,4,2,3三、判断题：(请在题干的括号内正确的打“ ，”，错的打“X”。每1分, 共10分)1、顺序表中的结点类型不能为结构体。 ( cuo )2、在单链表中，头结点是必不可少的。 (cuo)3、循环链表的结点结构与单链表的结点结构完全相同，只是结点间的连接方式不同。( dui )4、希尔排序方法是不稳定的。 (dui )5、只允许最下面的二层结点的度数小于2的二叉树是完全二叉树。()叉排序树查找和折半查找的时间性能相同。()7、n个结点的有向图，若它有n(n1)条边，则它一定是强连通的。 ( dui )8 、 多维数组元素之间的关系是线性的。 ( du

11、i )9、就平均查找长度而言，分块查找最小，折半查找次之，顺序查找最大。()10、在任何情况下，快速排序的效率总是最高的。 ()四、简答题：（30分，共6道小题，每题5分）1、已知一棵二叉树的前序序列为 ABDFCE,中序序列为DFBACE,请画 出该二叉树，并写出其后序序列。2、已知待排序文件各记录的排序码顺序如下7273712394160568请列出快速排序中第一趟排序过程及结果。3、下图所示的树中根结点为哪个？树的深度为多少？请将下图中的树转 换为二叉树。4、已知一稀疏矩阵如下图所示，试画出该稀疏矩阵的三元组顺序表和三 元组单链表。0 8 10 0 0 00 0 0 0 0 0-3 0

12、0 0 0 110 0 0 0 0 0匚0 1 0 0 0 0J5、给定叶结点权值：(1, 3, 5, 7, 8),构造哈夫曼树，并计算其带权 路径长度。6、从空树开始，逐个读入并插入下列关键字，构造一棵二叉排序树:(25, 66, 40, 97, 22, 15, 8, 11 )五、算法设计题：(30分，共3题，每题10分)要求：每题都要求先写出算法的设计思路，再写出实现该算法的C语言函数。函数名自定。1、编写链队列的进队列操作算法，链队列的定义如下：typedef struct SLNode elemtype Data;struct SLNode *Next;slnodetype;typedef struct slnodetype *Head;slnodetype *Rear;网qtype;2、编写函数InsertL(bt , x, Parent),其功能为：将数据域为 x的结点插 入二叉树bt中作为结点Parent的左孩子结点。如果结点 Parent原来有 左孩子则将结点 Parent原来的左孩子作为结点x的左孩子结点。二叉树中结点的数据类型和头结点定义如下：typedef struct BTreeNode elemtype Data;st