数据结构题目及答案

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

2、、在无向图中, 假设对于任意一对顶点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 *) int j;if(i*num+1

3、)printf(ni值不合法 !); return 0; for (j=*num;j=i;j-) ; /*数据元素依次后移*/List i=*;(*num)+;return 1; 在单链表中设置头结点的作用是_ 简化操作_。顺序存储构造使线性表中逻辑上相邻的数据元素在物理位置上也相邻。因此，这种表便于访问，设输入元素的顺序为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)，Pop(S)。由下标0开场且元素个数为n的一维数组实现循环队列时

4、，为实现下标变量m加1后在该数组的有效下标*围内循环，可采用的表达式是m_。对行下标由1到50、列下标由1到80的二维数组a，假设该数组的起始地址为2000且每个元素占2个存储单元，并以行为主序顺序存储，则元素a4568的存储地址为_；假设以列为主序顺序存储，则元素a4568的存储地址为_。设F是由T1、T2、T3三棵树组成的森林，与F对应得二叉树为B。T1、T2、T3的结点数分别为n1、n2和n3，则二叉树B的左子树中有_结点，二叉树右子树中有_个结点。设n0为哈夫曼树叶子结点的数目，则该哈夫曼树共有_个结点。具有10个顶点的无向图，边的总数最多为_。分块查找中，假设索引表对各块内均采用顺序

5、查找，有900个元素的线性表假设分成25块，其平均查找长度为_。假设一个待散列存储的线性表长度为n，用于散列的散列表长度为m，则装填因子为_ _。在堆排序和快速排序中，假设初始记录接近正序或反序，则选用_，假设初始记录无序，则最好用_。从一个无序序列建立一个堆的方法是：首先将待排序的所有关键字分放到一棵_的各个结点中，然后从i=的结点ki开场，逐步把ki-1,ki-2,k1为根的子树排成堆，直到以k1为根的树排成堆，就完成了建堆的过程。算法的重要特性有 有穷性 、确定性、可行性、输入和输出。二、单项选择题：每题1分，共10分1、对于一个头结点为head的带头结点的单链表，判定该表为空表的条件

6、A. head= =NULL; B. head-ne*t= =NULL;C. head-ne*t= = 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进展从小到大的排序,所需进展的关键字比拟总次数是( )A. 10 B. 15 C. 21

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

8、C. 2n+1 D. 2n-110、一个有n个顶点的无向图最多有 条边。A. n B. n(n-1) C. n(n-1)/2 D. 2n11.数据的存储构造包括顺序、散列和_4种根本类型。A. 向量 B. 数组 C.集合 D.索引下面关于线性表表达中的错误是_。A. 线性表采用顺序存储，必须占用一段地址连续的单元B. 线性表采用顺序存储，便于进展插入和删除操作C. 线性表采用链式存储，不必占用一段地址连续的单元D. 线性表采用链式存储，便于进展插入和删除操作栈和队列都是特殊的线性表，其特殊性在于_。A. 它们具有一般线性表所没有的逻辑特性B. 它们的存储构造比拟特殊C. 对它们的使用方法作了限

9、制!D. 它们比一般线性表更简单4.二维数组的行下标i=-3,-2,-1,0,5，列下标j=0,1,10，则该数组含有的元素个数为_ _。A. 88 B. 99 C. 80 D. 905假设对n个元素进展插入排序，则进展第i趟排序之前有序表中的元素个数为_。A. i B. i+1 C. i-1 D. 16一棵完全二叉树上有1001个结点，其叶子结点的个数是_。A. 250 B. 500 C. 505 D. AC都不对7设无向图的顶点个数为n，则该无向图最多有_条边。A. n-1 B. C. D. n8.存放元素的数组下标由1开场，对有18个元素的有序表作二分折半查找，则查找A3时比拟的下标序列

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

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

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