下载文档原格式
专升本《数据结构》_试卷_答案专升本《数据结构》一、（共75题,共150分）1. 数据的逻辑结构是由（）部分组成的。
（2分）A.2B.3C.4D.5标准答案：A2. 算法是对某一类问题求解步骤的有限序列，并具有（）个特性。
（2分）A.3B.4C.5D.6标准答案：C3. 队列的入队操作是在（）进行的。
（2分）A.队头B.队尾C.任意位置D.指定位置标准答案：B4. 队列的出队操作是在（）进行的。
（2分）A.队头B.队尾C.任意位置D.指定位置标准答案：A5. 数组通常采用顺序存储的优点是（）。
（2分）A.便于增加存储空间B.便于依据下标进行随机存取C.避免数据元素的移动D.防止下标溢出标准答案：B6. 下列给出的操作中，（）是允许对队列进行的操作。
（2分）A.删除队首元素B.取出最近进队的元素C.按元素大小排序D.中间插入元素标准答案：A7. 采用带头结点的单链表存储的线性表，若表长为n，在删除第号元素时，需要移动指针（）次。
（2分）A.k+1B.kC.k-1D.k-2标准答案：C8. 字符数组a[1..100]采用顺序存储，a[6]地址是517，则a的首地址为（）。
（2分）A.510B.512C.514D.516标准答案：B9. 深度为n的完全二叉树最多有（）个结点。
（2分）A.2n+1B.2n-1C.2nD.2n-1 10. 若二叉树对应的二叉链表共有n个非空链域，则该二叉树有（）个结点的二叉树。
（2分）A.n-1B.nC.n+1D.2n标准答案：A11. 下面叙述错误的是（）。
（2分）A.借助于队列可以实现对图的广度优先遍历B.二叉树中序遍历的序列是有序C.只有一个结点的二叉树的度为0D.空格串是指由1个或以上的空格符号组成的串标准答案：B12. 以下与数据的存储结构无关的术语是（）。
（2分）A.循环队列B.链表C.哈希表D.栈标准答案：D13. 在一个长度为n的链式栈中入栈实现算法的时间复杂度为（）。
数据结构试卷(一)三、计算题(每题 6分，共24 分) 3.已知一个图的顶点集 V 和边集E 分别为：V={1,2,3,4,5,6,7};E={(1,2)3,(1,3)5,(1,4)8,(2,5)10,(2,3)6,(3,4)15, (3,5)12,(3,6)9,(4,6)4,(4,7)20,(5,6)18,(6,7)25}; 用克鲁斯卡尔算法得到最小生成树，试写出在最小生成树中依次得到的各条边。
4.画出向小根堆中加入数据4, 2, 5, 8, 3时，每加入一个数据后堆的变化。
四、 阅读算法(每题 7分，共14分)1. LinkList mynote(LinkList L){//L 是不带头结点的单链表的头指针if(L&&L-> next){q=L ； L=L — >next ; p=L ;S1: while(p — >n ext) p=p — >next ; S2： p — >next=q ; q — >next=NULL ;}return L ;}请回答下列问题： (1 )说明语句S1的功能； (2) 说明语句组S2的功能；(3) 设链表表示的线性表为(a 1,a 2,…,a n ),写出算法执行后的返回值所表示的线性 表。
2. void ABC(BTNode * BT){if BT {ABC (BT->left); ABC (BT->right); cout<<BT->data<<''; } }该算法的功能是：五、 算法填空(共 8分) 二叉搜索树的查找 一谗归算法：bool Fi nd(BTreeNode* BST,ElemType & item){if (BST==NULL) return false; // 查找失败 else { if (item==BST->data){ item=BST->data;// 查找成功 return_______________________ ;}else if(item<BST->data) return Find( ,item);1.在如下数组A 中链接存储了一个线性表,A [0].next ，试写出该线性表。
2022年南京航空航天大学计算机科学与技术专业《数据结构与算法》科目期末试卷A（有答案）一、选择题1、用数组r存储静态链表，结点的next域指向后继，工作指针j指向链中结点，使j沿链移动的操作为（）。
A.j=r[j].nextB.j=j+lC.j=j->nextD.j=r[j]->next2、从未排序序列中依次取出一个元素与已排序序列中的元素依次进行比较，然后将其放在已排序序列的合适位置，该排序方法称为（）排序法。
A.插入B.选择C.希尔D.二路归并3、链表不具有的特点是（）。
A.插入、删除不需要移动元素B.可随机访问任一元素C.不必事先估计存储空间D.所需空间与线性长度成正比4、向一个栈顶指针为h的带头结点的链栈中插入指针s所指的结点时，应执行（）。
A.h->next=sB.s->next=hC.s->next=h;h->next=sD.s->next=h-next;h->next=s5、已知有向图G=(V，E)，其中V={V1，V2，V3，V4，V5，V6，V7}， E=｛<V1，V2>，<V1，V3>，<V1，V4>，<V2，V5>，<V3，V5>， <V3，V6>，<V4，V6>，<V5，V7>，<V6，V7>｝，G的拓扑序列是（）。
A.V1，V3，V4，V6，V2，V5，V7B.V1，V3，V2，V6，V4，V5，V7C.V1，V3，V5，V2，V6，V7D.V1，V2，V5，V3，V4，V6，V76、已知字符串S为“abaabaabacacaabaabcc”，模式串t为“abaabc”，采用KMP算法进行匹配，第一次出现“失配”（s!＝t）时，i＝j＝5，则下次开始匹配时，i和j的值分别（）。
A．i＝1，j＝0 B．i＝5，j＝0 C．i＝5，j＝2 D．i＝6，j＝27、循环队列放在一维数组A中，end1指向队头元素，end2指向队尾元素的后一个位置。
2022年金陵科技学院计算机科学与技术专业《数据结构与算法》科目期末试卷A（有答案）一、选择题1、下述文件中适合于磁带存储的是（）。
A.顺序文件B.索引文件C.哈希文件D.多关键字文件2、无向图G=(V，E)，其中：V={a，b，c，d，e，f}，E={(a，b)，(a， e)，(a，c)，(b，e)，(c，f)，(f，d)，(e，d)}，对该图进行深度优先遍历，得到的顶点序列正确的是（）。
A.a，b，e，c，d，fB.a，c，f,e，b，dC.a，e，b，c，f, dD.a，e，d，f，c，b3、某线性表中最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素，则采用（）存储方式最节省运算时间。
A.单链表B.仅有头指针的单循环链表C.双链表D.仅有尾指针的单循环链表4、已知有向图G=(V，E)，其中V={V1，V2，V3，V4，V5，V6，V7}， E=｛<V1，V2>，<V1，V3>，<V1，V4>，<V2，V5>，<V3，V5>， <V3，V6>，<V4，V6>，<V5，V7>，<V6，V7>｝，G的拓扑序列是（）。
A.V1，V3，V4，V6，V2，V5，V7B.V1，V3，V2，V6，V4，V5，V7C.V1，V3，V5，V2，V6，V7D.V1，V2，V5，V3，V4，V6，V75、已知串S='aaab'，其next数组值为（）。
A.0123B.1123C.1231D.12116、若元素a，b，c，d，e，f依次进栈，允许进栈、退栈操作交替进行，但不允许连续三次进行退栈操作，则不可能得到的出栈序列是（）。
7、排序过程中，对尚未确定最终位置的所有元素进行一遍处理称为一趟排序。
下列排序方法中，每一趟排序结束时都至少能够确定一个元素最终位置的方法是（）。
Ⅰ．简单选择排序Ⅱ．希尔排序Ⅲ．快速排序Ⅳ．堆排Ⅴ．二路归并排序A．仅Ⅰ、Ⅲ、Ⅳ B．仅Ⅰ、Ⅱ、Ⅲ C．仅Ⅱ、Ⅲ、Ⅳ D．仅Ⅲ、Ⅳ、Ⅴ8、一棵哈夫曼树共有215个结点，对其进行哈夫曼编码，共能得到（）个不同的码字。
2022年安徽农业大学计算机科学与技术专业《数据结构与算法》科目期末试卷A（有答案）一、选择题1、下述文件中适合于磁带存储的是（）。
A.顺序文件B.索引文件C.哈希文件D.多关键字文件2、无向图G=(V，E)，其中：V={a，b，c，d，e，f}，E={(a，b)，(a， e)，(a，c)，(b，e)，(c，f)，(f，d)，(e，d)}，对该图进行深度优先遍历，得到的顶点序列正确的是（）。
A.a，b，e，c，d，fB.a，c，f,e，b，dC.a，e，b，c，f, dD.a，e，d，f，c，b3、链表不具有的特点是（）。
A.插入、删除不需要移动元素B.可随机访问任一元素C.不必事先估计存储空间D.所需空间与线性长度成正比4、已知串S='aaab'，其next数组值为（）。
A.0123B.1123C.1231D.12115、已知有向图G=(V，E)，其中V={V1，V2，V3，V4，V5，V6，V7}， E=｛<V1，V2>，<V1，V3>，<V1，V4>，<V2，V5>，<V3，V5>， <V3，V6>，<V4，V6>，<V5，V7>，<V6，V7>｝，G的拓扑序列是（）。
A.V1，V3，V4，V6，V2，V5，V7B.V1，V3，V2，V6，V4，V5，V7C.V1，V3，V5，V2，V6，V7D.V1，V2，V5，V3，V4，V6，V76、下列关于无向连通图特性的叙述中，正确的是（）。
Ⅰ．所有的顶点的度之和为偶数Ⅱ．边数大于顶点个数减1 Ⅲ．至少有一个顶点的度为1A．只有Ⅰ B．只有Ⅱ C．Ⅰ和Ⅱ D．Ⅰ和Ⅲ7、下列选项中，不能构成折半查找中关键字比较序列的是（）。
A．500，200，450，180 B．500，450，200，180C．180，500，200，450 D．180，200，500，4508、已知一棵二叉树的前序遍历结果为ABCDEF，中序遍历结果为CBAEDF，则后序遍历结果为（）。
2022年湘南学院计算机科学与技术专业《数据结构与算法》科目期末试卷A（有答案）一、选择题1、n个结点的完全有向图含有边的数目（）。
A.n*nB.n(n+1)C.n/2D.n*(n-1)2、将线性表的数据元素进行扩充，允许带结构的线性表是（）。
A.串B.树C.广义表D.栈3、线性表的顺序存储结构是一种（）。
A.随机存取的存储结构B.顺序存取的存储结构C.索引存取的存储结构D.Hash存取的存储结构4、有六个元素6，5，4，3，2，1顺序入栈，下列不是合法的出栈序列的是（）。
A.543612B.453126C.346521D.2341565、用不带头结点的单链表存储队列，其队头指针指向队头结点，队尾指针指向队尾结点，则在进行出队操作时（）。
A.仅修改队头指针B.仅修改队尾指针C.队头、队尾指针都可能要修改D.队头、队尾指针都要修改6、若元素a，b，c，d，e，f依次进栈，允许进栈、退栈操作交替进行，但不允许连续三次进行退栈操作，则不可能得到的出栈序列是（）。
7、循环队列放在一维数组A中，end1指向队头元素，end2指向队尾元素的后一个位置。
假设队列两端均可进行入队和出队操作，队列中最多能容纳M－1个元素。
初始时为空，下列判断队空和队满的条件中，正确的是（）。
A．队空：end1＝＝end2；队满：end1＝＝（end2＋1）mod MB．队空：end1＝＝end2；队满：end2＝＝（end1＋1）mod （M－1）C．队空：end2＝＝（end1＋1）mod M；队满：end1＝＝（end2＋1） mod MD．队空：end1＝＝（end2＋1）mod M；队满：end2＝＝（end1＋1） mod （M－1）8、有n（n>0）个分支结点的满二叉树的深度是（）。
A.n2-1B.log2（n+1）+1C.log2（n+1）D.log2（n-l）9、一棵非空的二叉树的前序序列和后序序列正好相反，则该二叉树一定满足（）。
2022年池州学院计算机科学与技术专业《数据结构与算法》科目期末试卷A（有答案）一、选择题1、将线性表的数据元素进行扩充，允许带结构的线性表是（）。
A.串B.树C.广义表D.栈2、将两个各有N个元素的有序表归并成一个有序表，其最少的比较次数是（）。
A.NB.2N-1C.2ND.N-13、线性表的顺序存储结构是一种（）。
A.随机存取的存储结构B.顺序存取的存储结构C.索引存取的存储结构D.Hash存取的存储结构4、下列关于AOE网的叙述中，不正确的是（）。
A.关键活动不按期完成就会影响整个工程的完成时间B.任何一个关键活动提前完成，那么整个工程将会提前完成C.所有的关键活动提前完成，那么整个工程将会提前完成D.某些关键活动若提前完成，那么整个工程将会提前完成5、已知串S='aaab'，其next数组值为（）。
A.0123B.1123C.1231D.12116、已知字符串S为“abaabaabacacaabaabcc”，模式串t为“abaabc”，采用KMP算法进行匹配，第一次出现“失配”（s!＝t）时，i＝j＝5，则下次开始匹配时，i和j的值分别（）。
A．i＝1，j＝0 B．i＝5，j＝0 C．i＝5，j＝2 D．i＝6，j＝27、下列选项中，不能构成折半查找中关键字比较序列的是（）。
A．500，200，450，180 B．500，450，200，180C．180，500，200，450 D．180，200，500，4508、一棵哈夫曼树共有215个结点，对其进行哈夫曼编码，共能得到（）个不同的码字。
A.107B.108C.214D.2159、已知一棵二叉树的前序遍历结果为ABCDEF，中序遍历结果为CBAEDF，则后序遍历结果为（）。
A.CBEFDAB.FEDCBAC.CBEDFAD.不定10、在平衡二叉树中插入一个结点后造成了不平衡，设最低的不平衡结点为A，并已知A 的左孩子的平衡因子为0，右孩子的平衡因子为l，则应作（）型调整以使其平衡A.LLB.LRC.RLD.RR二、填空题11、在有n个顶点的有向图中，每个顶点的度最大可达______。
大学计算机《数据结构》试卷及答案
一、选择题(30分)
1．设一组权值集合W={2，3，4，5，6}，则由该权值集合构造的哈夫曼树中带权路径长度之和为（）。
(A) 20 (B) 30 (C) 40 (D) 45
2．执行一趟快速排序能够得到的序列是（）。
(A) [41，12，34，45，27] 55 [72，63]
(B) [45，34，12，41] 55 [72，63，27]
(C) [63，12，34，45，27] 55 [41，72]
(D) [12，27，45，41] 55 [34，63，72]
3．设一条单链表的头指针变量为head且该链表没有头结点，则其判空条件是（）。
(A) head==0 (B) head->next==0
(C) head->next==head (D) head!=0
4．时间复杂度不受数据初始状态影响而恒为O(nlog2n)的是（）。
(A) 堆排序(B) 冒泡排序(C) 希尔排序(D) 快速排序
5．设二叉树的先序遍历序列和后序遍历序列正好相反，则该二叉树满足的条件是（）。
(A) 空或只有一个结点(B) 高度等于其结点数
(C) 任一结点无左孩子(D) 任一结点无右孩子
6．一趟排序结束后不一定能够选出一个元素放在其最终位置上的是（）。
(A) 堆排序(B) 冒泡排序(C) 快速排序(D) 希尔排序
7．设某棵三叉树中有40个结点，则该三叉树的最小高度为（）。
(A) 3 (B) 4 (C) 5 (D) 6
8．顺序查找不论在顺序线性表中还是在链式线性表中的时间复杂度为（）。
(A) O(n) (B) O(n2) (C) O(n1/2) (D) O(1og2n)
9．二路归并排序的时间复杂度为（）。
(A) O(n) (B) O(n2) (C) O(nlog2n) (D) O(1og2n)
10. 深度为k的完全二叉树中最少有（）个结点。
(A) 2k-1-1 (B) 2k-1(C) 2k-1+1 (D) 2k-1
11.设指针变量front表示链式队列的队头指针，指针变量rear表示链式队列的队
尾指针，指针变量s指向将要入队列的结点X，则入队列的操作序列为（）。
(A) front->next=s；front=s；(B) s->next=rear；rear=s；
(C) rear->next=s；rear=s；(D) s->next=front；front=s；
12.设某无向图中有n个顶点e条边，则建立该图邻接表的时间复杂度为（）。
(A) O(n+e) (B) O(n2) (C) O(ne) (D) O(n3)
13.设某哈夫曼树中有199个结点，则该哈夫曼树中有（）个叶子结点。
(A) 99 (B) 100 (C) 101 (D) 102
14.设二叉排序树上有n个结点，则在二叉排序树上查找结点的平均时间复杂度
为（）。
(A) O(n) (B) O(n2) (C) O(nlog2n) (D) O(1og2n)
15.设用邻接矩阵A表示有向图G的存储结构，则有向图G中顶点i的入度为（）。
(A) 第i行非0元素的个数之和(B) 第i列非0元素的个数之和
(C) 第i行0元素的个数之和(D) 第i列0元素的个数之和
二、判断题(20分)
1．调用一次深度优先遍历可以访问到图中的所有顶点。
（）
2．分块查找的平均查找长度不仅与索引表的长度有关，而且与块的长度有关。
（）
3．冒泡排序在初始关键字序列为逆序的情况下执行的交换次数最多。
（）4．满二叉树一定是完全二叉树，完全二叉树不一定是满二叉树。
（）
5．设一棵二叉树的先序序列和后序序列，则能够唯一确定出该二叉树的形状。
（）
6．层次遍历初始堆可以得到一个有序的序列。
（）
7．设一棵树T可以转化成二叉树BT，则二叉树BT中一定没有右子树。
（）8．线性表的顺序存储结构比链式存储结构更好。
（）
9．中序遍历二叉排序树可以得到一个有序的序列。
（）
10.快速排序是排序算法中平均性能最好的一种排序。
（）
三、填空题(30分)
1．for(i=1，t=1，s=0；i<=n；i++) {t=t*i；s=s+t；}的时间复杂度为_________。
2．设指针变量p指向单链表中结点A，指针变量s指向被插入的新结点X，则进行插入操作的语句序列为__________________________（设结点的指针域为next）。
3．设有向图G的二元组形式表示为G =（D，R），D={1，2，3，4，5}，R={r}，r={<1,2>，<2,4>，<4,5>，<1,3>，<3,2>，<3,5>}，则给出该图的一种拓扑排序序列__________。
4．设无向图G中有n个顶点，则该无向图中每个顶点的度数最多是_________。
5．设二叉树中度数为0的结点数为50，度数为1的结点数为30，则该二叉树中总共有_______个结点数。
6．设F和R分别表示顺序循环队列的头指针和尾指针，则判断该循环队列为空的条件为_____________________。
7．设二叉树中结点的两个指针域分别为lchild和rchild，则判断指针变量p所指向的结点为叶子结点的条件是
_____________________________________________。
8．简单选择排序和直接插入排序算法的平均时间复杂度为___________。
9．快速排序算法的空间复杂度平均情况下为__________，最坏的情况下为__________。
10.散列表中解决冲突的两种方法是_____________和_____________。
四、算法设计题(20分)
１．设计在顺序有序表中实现二分查找的算法。
２．设计判断二叉树是否为二叉排序树的算法。
３．在链式存储结构上设计直接插入排序算法
参考答案
一、选择题
1．D 2．A 3．A 4．A 5．D 6．D 7．B 8．A 9．C 10．B 11．C 12．A 13．B 14．D 15．B
二、判断题
1．错2．对3．对4．对5．错
6．错7．对8．错9．对10．对
三、填空题
1. O(n)
2. s->next=p->next; p->next=s
3. (1，3，2，4，5)
4. n-1
5. 129
6. F==R
7. p->lchild==0&&p->rchild==0
8. O(n2)
9. O(nlog2n)，O(n)
10. 开放定址法，链地址法
四、算法设计题
1. 设计在顺序有序表中实现二分查找的算法。
struct record {int key; int others;};
int bisearch(struct record r[ ], int k)
{
int low=0,mid,high=n-1;
while(low<=high)
{
mid=(low+high)/2;
if(r[mid].key==k) return(mid+1); else if(r[mid].key>k) high=mid-1; else low=mid+1;
}
return(0);
}
2. 设计判断二叉树是否为二叉排序树的算法。
int minnum=-32768,flag=1;
typedef struct node{int key; struct node *lchild,*rchild;}bitree;
void inorder(bitree *bt)
{
if (bt!=0) {inorder(bt->lchild); if(minnum>bt->key)flag=0; minnum=bt->key;inorder(bt->rchild);}
}
3. 在链式存储结构上设计直接插入排序算法
void straightinsertsort(lklist *&head)
{
lklist *s,*p,*q; int t;
if (head==0 || head->next==0) return;
else for(q=head,p=head->next;p!=0;p=q->next)
{
for(s=head;s!=q->next;s=s->next) if (s->data>p->data) break;
if(s==q->next)q=p;
else{q->next=p->next; p->next=s->next; s->next=p; t=p->data;p->data=s->data;s->data=t;}
}
}。
