数据结构(A卷)【含答案】

中国矿业大学2011-2012学年《数据结构》试卷（A卷）（考试时间：100分钟）一. 填空（每空2分，共40分）1. 数据结构式具有相同性质的数据元素的（1）。

2. 通常程序在调用另一个程序时，都需要使用一个（2）来保存被调用程序内分配的局部变量、形式参数的存储空间以及返回地址。

3. 有6行8列的二维数组A，每个元素用相邻的6个字节存储，存储器按字节编址，已知A的起始存储地址（基址）为1000，在行优先存储和列优先存贮情况下A[5,5]的存储地址分别为__（3）_____,_____(4)____。

4. 完全二叉树第4 个节点的父节点是第 (5) 节点，左孩子是第 (6) 个节点。

如果该二叉树有10层，则共有 (7) 个节点。

5. 请描述在循环队列Q中，队头和队尾指针分别由front和rear表示，该队列有10个存储空间，判断队空和队满的条件分别分：_____(8)________,_______(9)_________。

6. 字符串t=”child”，s=”cake”，请写出下列函数的结果：StrLength(t) =（10）__;Concat(SubString(s,3,1)，SubString(t,2,2))=____（11）___。

7. 一棵二叉树为则后序序列为（12），中序序列为（13），先序序列为__（14）____。

8. 请用数据序列{53，17，12，66，58，70，87，25，56，60 }构造一棵二叉排序树_(15）_。

9.。

一个栈输入的序列式1,2,3，则可能的且以2为开头的输出序列是 (16) ，不可能的序列是____（17）____。

10. 有n个结点的无向完全图的边数分别为_______(18)_______。

11. 要从数据：2，3，4，8，9，11，13查找11，若采用折半查找法，则在（19）次比较后，才找到该数据。

12. 在直接插入排序、希尔排序、冒泡排序和快速排序中，平均情况下（20）_____最快。

数据结构期末考试试卷（A卷）第一学期开课单位：软件学院 ,考试形式：闭、开卷,允许带入场I。

基本概念部分(共60分）1 下图所示是单链表结点的插入过程，在fence结点后面插入一个值为10的ltmp结点，已知fence—>next是指向fence的后继结点，请把这一插入过程用代码表示出来：（6分)这一过程的代码:ltmp—〉next = fence—>next；fence—>next = ltmp;2 下图所示是双链表结点的删除过程，在fence结点后面删除一个值为23的结点，已知fence->next是指向fence的后继结点，fence —>prev是指向fence的前驱结点,ltmp是一个值为NULL的链表结点指针，请把这一删除过程用代码表示出来：（8分)这一过程的代码：ltmp = fence—〉next;fence-〉next = ltmp—>next;ltmp->next—>prev = fence；3 画出下图中的BST加上值5以后的形状.(6分）4 画出下图所示图的相邻矩阵表示(假设下面的表格是一个二维数组，请在表格中填入正确的数值）.（8分）5 给出下图从顶点1开始的DFS 树。

(8分）6（最小生成树）。

(8分)7 :(8分）］， int n){for （int i = 0; i 〈 n ； i++）{； j++)｛if(A ［i ｛ tmp = A[i ］;A ［i ］ = A ［j ］；A[j] = tmp; } }//外层循环，打印一下中间结果for （int k = 0； k < n; k++) printf(” %d",A[k］）; printf （”\n”）; } ｝int A［] = { 9, 12，3,7，90，15};8 给出从下图的最大值堆中删除最大元素后得到的堆.（8分）或II。

1//合并两个有序的单链表为一个新的有序的单链表，//传入参数为两个有序的单链表，返回合并后的有序表。

河南师范大学软件学院2017--2018学年度第一学期 2016级计算机专业期末考试《数据结构》A 卷1. 在数据结构中，从逻辑上可以把数据结构分成（ C ）。

A ．动态结构和静态结构B ．紧凑结构和非紧凑结构C ．线性结构和非线性结构D ．内部结构和外部结构2. 算法的时间复杂度取决于（ D ）。

A ．问题的规模B ．待处理数据的初态C ．计算机的配置D ．A 和B3. 与数据元素本身的形式、内容、相对位置、个数无关的是数据的（ C ）。

A ．存储结构B ．存储实现C ．逻辑结构D ．运算实现4. 线性表L 在（ B ）情况下适用于使用链式结构实现。

A ．需经常修改L 的结点值B ．需不断对L 进行删除、插入C ．L 中含有大量的结点D ．L 中结点结构复杂5. 单链表的存储密度（ C ）。

A ．大于1B ．等于1C ．小于1D ．不能确定6. 线性表L=(a1，a2,……an)，下列说法正确的是（ D ）。

A ．每个元素都有一个直接前驱和一个直接后继; B ．线性表中至少有一个元素;C ．表中诸元素的排列必须是由小到大或由大到小;D ．除第一个和最后一个元素外，其余每个元素都有一个且仅有一个直接前驱和直接后继。

7. 在单链表中，要将s 所指结点插入到p 所指结点之后，其语句应为（ D ）。

A ．s->next=p+1; p->next=s;B ．(*p).next=s; (*s).next=(*p).next;C ．s->next=p->next; p->next=s->next;D ．s->next=p->next; p->next=s;8. 栈中元素的进出原则是（ B ）。

A 、先进先出 B 、后进先出 C 、栈空则进 D 、栈满则出9. 若让元素1，2，3，4，5依次进栈，则出栈次序不可能出现在（ C ）种情况。

A ．5，4，3，2，1 B ．2，1，5，4，3 C ．4，3，1，2，5 D ．2，3，5，4，110. 以下数据结构中，（ A ）是非线性数据结构。

数据结构试卷一、填空殖（每空1分共20分)1.数据的物理结构主要包括___顺序存储结构__________和_链式_____________两种情况。

2.设一棵完全二叉树中有500个结点，则该二叉树的深度为_______9___;若用二叉链表作为该完全二叉树的存储结构，则共有______501_____个空指针域.3.设输入序列为1、2、3，则经过栈的作用后可以得到_____6______种不同的输出序列。

4.设有向图G用邻接矩阵A[n][n]作为存储结构，则该邻接矩阵中第i行上所有元素之和等于顶点i的___出度_____,第i列上所有元素之和等于顶点i的____入度____。

5.设哈夫曼树中共有n个结点,则该哈夫曼树中有___0_____个度数为1的结点。

6.设有向图G中有n个顶点e条有向边，所有的顶点入度数之和为d,则e和d的关系为____e=d_____。

7.____中序______遍历二叉排序树中的结点可以得到一个递增的关键字序列(填先序、中序或后序）.8.设查找表中有100个元素,如果用二分法查找方法查找数据元素X,则最多需要比较_____7___次就可以断定数据元素X是否在查找表中。

9.不论是顺序存储结构的栈还是链式存储结构的栈，其入栈和出栈操作的时间复杂度均为______1______。

10.设有n个结点的完全二叉树，如果按照从自上到下、从左到右从1开始顺序编号,则第i个结点的双亲结点编号为___i/2_________,右孩子结点的编号为____2i+1_______。

11.设一组初始记录关键字为（72，73,71，23,94,16,5），则以记录关键字72为基准的一趟快速排序结果为_____5 16 71 23 72 94 73______。

12.设有向图G中有向边的集合E=｛〈1，2〉，<2,3>，〈1，4〉，〈4,2>，〈4，3〉｝，则该图的一种拓扑序列为___1 4 2 3___。

2003-2004学年第二学期数据结构期终试卷（A卷）（考试时间100分钟）班级姓名学号得分一、单项选择题（本大题共15小题，第小题2分，共30分）在每小题列出的四个选项中只有一个符合题目要求，请将其代码填在题后的括号内。

错选或未选均无分。

1. 算法必须具备输入、输出和[ C ]A. 计算方法B. 排序方法C．解决问题的有限运算步骤 D. 程序设计方法2. 有n个节点的顺序表中，算法的时间复杂度是O(1)的操作是[ A ]A.访问第i个节点（1≤i≤n）B.在第i个节点后插入一个新节点（1≤i≤n）C.删除第i个节点（1≤i≤n）D.将n个节点从小到大排序3．单链表的存储密度[ C] A．大于1 B. 等于1C．小于1 D. 不能确定4．设将整数1,2,3,4,5依次进栈，最后都出栈，出栈可以在任何时刻（只要栈不空）进行，则出栈序列不可能是[ B] A．23415 B. 54132C．23145 D. 154325. 循环队列SQ的存储空间是数组d[m]，队头、队尾指针分别是front和rear，则执行出队后其头指针front值是[ D ] A．front=front+1 B. front=(front+1)%(m-1)C. front=(front-1)%mD. front=(front+1)%m6. 在一个具有n个结点的有序单链表中插入一个新结点并仍然保持有序的时间复杂度是[ B ]A. O(1)B. O(n)C. O(n2)D. O(nlogn)7. 设二维数组A[0..m-1][0..n-1]按行优先顺序存储，则元素A[i][j]的地址为A．LOC(A[0][0])+(i*m+j) B．LOC(A[0][0])+(i*n+j)C.LOC(A[0][0])+[(i-1)*n+j-1]D. LOC(A[0][0])+[(i-1)*m+j-1]8. 一个非空广义表的表头[ D ]A．一定是子表 B. 一定是原子C．不能是子表 D. 可以是原子，也可以是子表9．具有n个节点的完全二叉树的深度为[ A ] A．⎡log2(n+1)⎤ -1 B. log2n+1C. log2nD. ⎣log2n⎦10. 若要惟一地确定一棵二叉树，只需知道该二叉树的[ D ]A．前序序列 B. 中序序列C．前序和后序序列 D. 中序和后序序列11．在一个无向图中，所有顶点的度数之和等于图的边数的倍[ C ] A．1/2 B. 1C. 2D. 412. 拓扑排序运算只能用于[ C ]A．带权有向图 B. 连通无向图C．有向无环图 D. 无向图13．在所有排序方法中，关键字比较的次数与记录的初始排列次序无关的是[ D ] A．希尔排序 B. 冒泡排序C．插入排序 D. 选择排序14．下列排序算法中时间复杂度不受数据初始状态影响，恒为O(n2)的是[ C ] A．堆排序 B. 冒泡排序C．直接选择排序 D. 快速排序15．二分查找要求节点[ A ] A．有序、顺序存储 B. 有序、链接存储C．无序、顺序存储 D. 无序、链接存储二、填空题（本大题共10小题，每小题2分，共20分）不写解答过程，将正确的答案写在每小题的空格内。

生答题不得过此线··密····························封·························线···························· 院系 专业年级 班级 姓名 学号··················装····························订·························线···························· 一、选择填空题(每题只有1个正确答案，每题1分，共20分)1．从逻辑上可以把数据结构分为（ ）两大类。

数据结构试题A答案陕西科技⼤学试题纸（A参考答案及评分标准）课程数据结构班级信息、数学05学号姓名请在每⼩题的四个备选答案中，选出⼀个正确的答案，并将其号码填在括号内。

1.设⼀个栈的输⼊序列为1，2，3，4，则借助⼀个栈所得的输出序列不可能是（D）。

A．1，2，3，4 B．4，3，2，1C．1，3，4，2 D．4，1，2，32. 设有80⾏的⼆维数组A[80][60]，其元素长度为4字节，按⾏优先顺序存储，基地址为300，则元素A[18][25]的存储地址为（D）。

A．3800 B．4376 C．3900 D．47203. 将⼀棵有100个节点的完全⼆叉树从根这⼀层开始，每⼀层上从左到右依次对结点进⾏编号，根节点的编号为0，则编号为49的结点的左孩⼦编号为（B）。

A．98 B．99 C．50 D．494. 在长度为n的顺序存储的线性表中，删除第i个元素（1≤i ≤n）时，需要从前向后依次前移（A）个元素。

A．n-i B．n-i+1 C．n-i-1 D．i5. 栈的插⼊和删除操作在（A）进⾏。

A．栈顶B．栈底C．任意位置D．指定位置6. 链表适⽤于（A）查找。

A．顺序B．⼆分法C．⼆分法、顺序D．随机7. 深度为6(根结点的层次为1)的⼆叉树⾄多有（D）个结点。

A．64 B．32 C．31 D．638. ⽤邻接表表⽰图进⾏⼴度优先遍历时，通常是采⽤（B）来实现算法的。

A．栈B．队列C．树D．图9. 设有两个串ｐ和ｑ，求ｑ在ｐ中⾸次出现的位置的运算称作（B）。

A．连接B．模式匹配C．求⼦串D．求串长10.若某线性表中最常⽤的操作是取第i个数据元素，则采⽤（D）存储⽅式最节省时间。

A．单链表B．双链表C．单向循环D．顺序表11.三个结点可构成（D）个不同形态的⼆叉树。

A．2 B．3 C．4 D．512.下列关键字序列中，（D）是堆。

A．16,72,31,23,94,53 B．94,23,31,72,16,53C．16,53,23,94,31,72 D．16,23,53,31,94,7213.把⼀棵树转换为⼆叉树后，这棵⼆叉树的形态是（A）。

三、程序填空题（本题共、链式表表示和实现线性表的部分程序如下，请在程序空白处填上适当的语句：//线性表的单链表存储结构typedef struct LNode{线 订 装数据结构与算法A卷答案一、选择题：（本题共20小题，每题2分，共40分）1-5：CA、DBCC 6-10：BDDAB 11-15：AABBA 16-20：CCCBC二、分析运算题（本题共5小题，每题6分，共30 分）1、解答：（1）选链式存储结构。

它可以动态申请内存空间，不受表长度（即表中元素个数）的影响，插入、删除的时间复杂性为O(1)；（2）选顺序存储结构。

顺序表可以随机存取，时间复杂性为O(1)。

2.CBADECBAEDCBEDACBDAECBDEA每对一个得1分，全对得6分，写错一个倒扣1分。

3.（3分）先序遍历序列：+-A/×BCD/EF （3分）4.（3分）后序遍历序列为：BHECIGFA D （3分）（1）（2分）（2）（2分）（3）（2分）三、程序填空题（本题共10空，每空2分，共20分）(1)p = L(2)p->next(3)p->next=q->next(4)free(q)（5）NULL或=NULL（6）printf(“%c”,BT->data)（7）Inorder(BT->right)(8) Push(S, exp[i]) 或 Push(S,‘（’)(9) GetTop(S)= ='('(10) Pop(S,e)四、算法设计题（本题共1小题，共10分）1、（10分）算法如下：答：void quickpass(sqlist r){int i=0; j=r.length-1; x=r.elem[0];while(i<j){while(i<j && r.elem[j]>x) j=j-1;if(i<j){r.elem[i]=r.elem[j];i=i+1;} while(i<j && r.elem[i]<x) i=i+1;if(i<j){r.elem[j]=r.elem[i];j=j-1;} }r.elem[i]=x;}。