大工17春《数据结构》在线作业3答案

复习（一）一、选择题1．下面关于线性表的叙述错误的是（D）。

A、线性表采用顺序存储必须占用一片连续的存储空间B、线性表采用链式存储不必占用一片连续的存储空间C、线性表采用链式存储便于插入和删除操作的实现D、线性表采用顺序存储便于插入和删除操作的实现2．设哈夫曼树中的叶子结点总数为m，若用二叉链表作为存储结构，则该哈夫曼树中总共有（B ）个空指针域。

A、 2m-1B、 2mC、 2m+1D、 4m3．设顺序循环队列Q[0：M-1]的头指针和尾指针分别为F和R，头指针F总是指向队头元素的前一位置，尾指针R总是指向队尾元素的当前位置，则该循环队列中的元素个数为（C）。

A、 R-FB、 F-RC、(R-F+M)％MD、(F-R+M)％M4．设某棵二叉树的中序遍历序列为ABCD，前序遍历序列为CABD，则后序遍历该二叉树得到序列为（A）。

A、 BADCB、 BCDAC、 CDABD、CBDA5．设某完全无向图中有n个顶点，则该完全无向图中有（A ）条边。

A、 n(n-1)/2B、 n(n-1)C、 n2D、 n2-16．设某数据结构的二元组形式表示为A=(D，R)，D={01，02，03，04，05，06，07，08，09}，R={r}，r={<01，02>，<01，03>，<01，04>，<02，05>，<02，06>，<03，07>，<03，08>，<03，09>}，则数据结构A是（B ）。

A、线性结构B、树型结构C、物理结构D、图型结构7．下面程序的时间复杂为（B）for（i=1，s=0；i<=n；i++）{t=1；for(j=1；j<=i；j++) t=t*j；s=s+t；}A、 O(n)B、 O(n2)C、 O(n3)D、 O(n4)8．设指针变量p指向单链表中结点A，若删除单链表中结点A，则需要修改指针的操作序列为（A ）。

第3章作业答案一、填空1. 向量、栈和队列都是线性结构，可以在向量的任何位置插入和删除元素；对于栈只能在栈顶插入和删除元素；对于队列只能在队尾插入和队首删除元素。

2. 栈是一种特殊的线性表，允许插入和删除运算的一端称为栈顶。

不允许插入和删除运算的一端称为栈底。

3. 队列是被限定为只能在表的一端进行插入运算，在表的另一端进行删除运算的线性表。

4.在具有n个单元的循环队列中，队满时共有n-1 个元素。

设有4个数据元素a1、a2、a3和a4，对他们分别进行栈操作或队操作。

在进栈或进队操作时，按a1、a2、a3、a4次序每次进入一个元素。

假设栈或队的初始状态都是空。

现要进行的栈操作是进栈两次，出栈一次，再进栈两次，出栈一次；这时，第一次出栈得到的元素是 A ，第二次出栈得到的元素是 B 是；类似地，考虑对这四个数据元素进行的队操作是进队两次，出队一次，再进队两次，出队一次；这时，第一次出队得到的元素是 C ，第二次出队得到的元素是 D 。

经操作后，最后在栈中或队中的元素还有E个。

供选择的答案：A～D：①a1 ②a2 ③a3 ④a4E：①1 ②2 ③3 ④0答：ABCDE＝2, 4, 1, 2, 2栈是一种线性表，它的特点是 A 。

设用一维数组A[1,…,n]来表示一个栈，A[n]为栈底，用整型变量T指示当前栈顶位置，A[T]为栈顶元素。

往栈中推入（PUSH）一个新元素时，变量T的值 B ；从栈中弹出（POP）一个元素时，变量T的值 C 。

设栈空时，有输入序列a，b，c，经过PUSH，POP，PUSH，PUSH，POP操作后，从栈中弹出的元素的序列是 D ，变量T的值是 E 。

供选择的答案：A：①先进先出②后进先出③进优于出④出优于进⑤随机进出B，C：①加1 ②减1 ③不变④清0 ⑤加2 ⑥减2D：①a,b ②b,c ③c,a ④b,a ⑤c,b ⑥a,cE：①n+1 ②n+2 ③n ④n-1 ⑤n-2答案：ABCDE=2, 2, 1, 6, 4在做进栈运算时，应先判别栈是否 A ；在做退栈运算时，应先判别栈是否 B 。

大工17秋《数据结构》在线作业1-0004
试卷总分:100得分:100
一、单选题(共10道试题,共50分)
1.下面关于串的概念的叙述中错误的是()。

（5分）
A.串是字符的有限序列
B.串既可以采用顺序存储，也可以采用链式存储
C.空串是由空格构成的串
D.模式匹配是串的一种重要运算
正确答案:C
2.一个有n个结点的有序单链表中,删除一个结点并仍然使链表有序的时间复杂度是()。

（5分）
A.O(1)
B.O(n)
C.O(n^2)
D.O(nlog2n)
正确答案:B
3.序列{a,b,c,d}顺序进栈,其出栈的顺序不可能为()。

（5分）
A.dcba
B.cdab
C.adcb
D.abcd
正确答案:B
4.以下四种数据结构中()不是线性结构。

（5分）
A.队列
B.线性表
C.栈
D.二叉树
正确答案:D
5.最适合用做链式队列的链表是()。

（5分）
A.带队首指针和队尾指针的循环单链表
B.带队首指针和队尾指针的非循环单链表
C.只带队首指针的非循环单链表
D.只带队首指针的循环单链表
正确答案:B。

数据结构c语言版第三版习题解答数据结构 C 语言版第三版习题解答在学习计算机科学与技术的过程中，数据结构是一门非常重要的基础课程。

而《数据结构C 语言版第三版》更是众多教材中的经典之作。

其中的习题对于我们理解和掌握数据结构的概念、原理以及算法实现起着至关重要的作用。

接下来，我将为大家详细解答这本书中的一些典型习题。

首先，让我们来看一道关于线性表的习题。

题目是这样的：设计一个算法，从一个有序的线性表中删除所有其值重复的元素，使表中所有元素的值均不同。

对于这道题，我们可以采用双指针的方法来解决。

定义两个指针 p和 q，p 指向线性表的开头，q 从 p 的下一个位置开始。

当 q 所指向的元素与 p 所指向的元素相同时，我们就将 q 所指向的元素删除，并将 q 向后移动一位。

当 q 所指向的元素与 p 所指向的元素不同时，我们将 p 向后移动一位，并将 q 所指向的元素赋值给 p 所指向的位置，然后再将 q 向后移动一位。

当 q 超出线性表的范围时，算法结束。

下面是用 C 语言实现的代码：｀｀｀cvoid removeDuplicates(int arr, int n) ｛int p ＝ 0, q ＝ 1;while （q ＜ n) ｛if （arrp ＝＝ arrq) ｛for （int i ＝ q; i ＜ n 1; i+＋）｛arri ＝ arri ＋ 1;｝（n)；｝ else ｛p+＋；arrp ＝ arrq;｝q+＋；｝｝｀｀｀再来看一道关于栈的习题。

题目是：利用栈实现将一个十进制数转换为八进制数。

我们知道，将十进制数转换为八进制数可以通过不断除以 8 取余数的方法来实现。

而栈的特点是后进先出，正好适合存储这些余数。

以下是 C 语言实现的代码：｀｀｀cinclude ＜stdioh>include ＜stdlibh>define MAX_SIZE 100typedef struct ｛int top;int dataMAX_SIZE;｝ Stack;／／初始化栈void initStack(Stack s) ｛s>top ＝－1;｝／／判断栈是否为空int isEmpty(Stack s) ｛return s>top ＝＝－1;｝／／判断栈是否已满int isFull(Stack s) ｛return s>top ＝＝ MAX_SIZE 1;｝／／入栈操作void push(Stack s, int element) ｛if （isFull(s)）｛printf(＂Stack Overflow!＼n"）；return;｝s>data+＋s>top ＝ element;｝／／出栈操作int pop(Stack s) ｛if （isEmpty(s)）｛printf(＂Stack Underflow!＼n"）；return －1;｝return s>datas>top;｝／／将十进制转换为八进制void decimalToOctal(int decimal) ｛Stack s;initStack(＆s)；while （decimal!＝ 0) ｛push(＆s, decimal ％ 8)；decimal ／＝ 8;｝while （！isEmpty(＆s)）｛printf(＂％d"， pop(＆s)）；｝printf(＂＼n"）；｝int main(）｛int decimal;printf(＂请输入一个十进制数: ＂）；scanf(＂％d"，＆decimal)；printf(＂转换后的八进制数为: ＂）；decimalToOctal(decimal)；return 0;｝｀｀｀接下来是一道关于队列的习题。

西安交通大学17年3月课程考试《数据结构》作业考核试题一、单选题（共30 道试题，共60 分。

）1. 与数据元素本身的形式、内容、相对位置、个数无关的是数据的（）A. 存储结构B. 逻辑结构C. 算法D. 操作正确答案：B2. 设一棵完全二叉树中有65个结点，则该完全二叉树的深度为（）。

A. 8B. 7C. 6D. 5正确答案：B3. 利用直接插入排序法的思想建立一个有序线性表的时间复杂度为（）。

A. O(n)B. O(nlog2n)C. O(n)D. O(1og2n)正确答案：C4. 栈的插入和删除操作在（）进行。

A. 栈顶B. 栈底C. 任意位置D. 指定位置正确答案：A5. 二路归并排序的时间复杂度为（）。

A. O(n)B. O(n)C. O(nlog2n)D. O(1og2n)正确答案：C6. 设某强连通图中有n个顶点，则该强连通图中至少有（）条边。

A. n(n-1)B. n+1C. nD. n(n+1)正确答案：C7. 设一个顺序有序表A[1:14]中有14个元素，则采用二分法查找元素A[4]的过程中比较元素的顺序为（）A. A[1]，A[2]，A[3]，A[4]B. A[1]，A[14]，A[7]，A[4]C. A[7]，A[3]，A[5]，A[4]D. A[7]，A[5]，A[3]，A[4]正确答案：C8. 下列各种排序算法中平均时间复杂度为O（n）是（）。

A. 快速排序B. 堆排序C. 归并排序D. 冒泡排序正确答案：D9. 如下陈述中正确的是（）A. 串是一种特殊的线性表B. 串的长度必须大于零C. 串中元素只能是字母D. 空串就是空白串正确答案：A10. 设有一个二维数组A[m][n]，假设A[0][0]存放位置在644(10)，A[2][2]存放位置在676(10)，每个元素占一个空间，问A[3][3](10)存放在什么位置（）？脚注(10)表示用10进制表示。

A. 688B. 678C. 692D. 696正确答案：C11. 适于对动态查找表进行高效率查找的组织结构是（）A. 有序表B. 分块有序表C. 三叉排序树D. 线性链表正确答案：C12. 设某完全无向图中有n个顶点，则该完全无向图中有（）条边。

Ch3栈和队列一．选择和填空：1．一个栈的入栈序列是a，b，c，d，e，则栈的可能的出栈序列是( D )。

A．edcab B．decab C．dceab D．abcde2．若已知一个栈的入栈序列是1，2，3，…，n，其输出序列为p1，p2，p3，…，pn，若p1=n，则pi为(n-i+1)。

3．栈结构通常采用的两种存储结构是(顺序存储结构和链式存储结构)。

4．判定一个顺序栈S为空的条件是(最多元素为m)(S.top=0或S.top=S.base)。

5．判定一个顺序栈S为满的条件是(最多元素为m)(S.top=m或S.top-S.base=m)。

6．栈的特点是(先进后出)，队列的特点是(先进先出)。

7．一个队列的入对序列是a，b，c，d，e，则出队序列是(a，b，c，d，e)。

8．判定一个顺序队列Q(最多元素为m)为空的条件是(Q.front=Q.rear=0，…，m)。

9．判定一个顺序队列Q(最多元素为m)为满的条件是(Q.rear-Q.front=m或Q.rear=m，Q.front=0)。

10．判定一个循环队列Q(最多元素为m)为空的条件是(Q.front=Q.rear=0，…m-1)。

11．判定一个循环队列Q(最多元素为m)为满的条件是(Q.front=(Q.rear+1)%m)。

12．循环队列用数组Q[0，m-1]存放其元素值，已知其头尾指针分别是front和rear，则当前队列中的元素个数是((Q.rear-Q.front+m)%m)。

13．栈和队列的共同点是(是限定性的线性结构，只能在端点处进行插入删除操作)。

14．线性表、栈和队列都是(线性)结构，可以在线性表的(任何)位置插入和删除元素，对于栈，只能在(栈顶)位置插入和删除元素，对于队列只能在(队尾)插入元素和在(队头)删除元素。

15．向栈中压入元素的操作是(先压入元素，后移动指针或*S.top++=e)。

16．从栈中弹出元素的操作是(先移动指针，后弹出元素或e= - -*S.top)。

一、单选题：C D B A A A C B C C二、填空题：n n/2 7 n2+2n3+…..+(m-1)n m+1 只有根节点的二叉树逆序1000000 2000 最大24三、应用题1、参考答案A B C D E F G H10 001 11 0001 0110 0111 010 00002、0 1 2 3 4 5 6 7 8 9 1012 100 25 16 17 18 8 40 7(1) (2) (1) (1) (1) (1) (1) （3）(4)搜索成功的平均搜索长度为ASL succ = 19(1 + 2+ 1 + 1 + 1 + 1 +1+ 3+ 4) = 533、4、最小生成树或最小生成树不唯一，有两棵，如上所示。

5、四、算法设计题1、void Bucketsort ( ElementType A[ ], int N )12 45635 6 11 1618 1 24563{int Counter[ 3 ];int i, j, k;for ( i = 0; i < 3; i++ )Counter[ i ] = 0;for ( i = 0, i < N; i++ ) {if ( A[ i ] == false )Counter[ 0 ] ++;elseif ( A[ i ] == maybe )Counter[ 1 ] ++;elseCounter[ 2 ] ++;}k = 0;for ( i = 0; i < Counter[ 0 ]; i++ )A[ i ] = false;k += Counter[ 0 ];for ( i = 0; i < Counter[ 1 ]; i++ )A[ k+i ] = maybe;k += Counter[ 1 ];for ( i = 0; i < Counter[ 2 ]; i++ )A[ k+i ] = true;}2、int BinaryTree<Type> :: leaf ( BinTreeNode<Type> * ptr ) {if ( ptr == NULL ) return 0;else if ( ptr->leftChild == NULL && ptr->rightChild == NULL ) return 1;else return leaf ( ptr->leftChild ) + leaf ( ptr->rightChild );}3、int max=0;int Find_All_Path(Graph *G,int S,int T, int K)/{G->setMark(S,VIEITED);if(S==T) //找到了一条简单路径{ if (max<K) max=K; return(max); }elsefor(int p=G->first(S);p<G->n();p=G->next(S,p){if(G->getMark(p)==UNVISITED) Find_All_Path(G,p,T,k+1); //继续寻找}G->setMark(S,UNVIEITED); }。

春理工大学
2017年全国硕士研究生统一入学考试自命题试题
********************************************************************************************
学科与专业名称：计算机科学技术学院所有专业
考试科目代码与名称：809数据结构
】考试科目：数据结构共4 页，第1页
考试科目：数据结构共 4 页，第2 页
三．简答题（共60分）
1.已知一棵二叉树的中序为CDBAGFHE, 后序为DCBGHFEA,画出这棵二叉树的先序和后序线索二叉树.(6分)
2.对下列关键字序列进行快速排序(从小至大) (48, 38, 65, 95, 73, 13, 27, 50)要求给出快速排序的算法思想,并画出排序过程示意图。

（10）
3.如图所示，求出改图的最短路径和拓扑排序，用2种方法画出图二的最小生出树。

（14）
图一图二
4.已知输入关键字序列为（100,90,120,60,78,35,42,31,15）地址区间为0～11。

设计一个哈希表函数把上述关键字散到0～11中，画出散列表（冲突用线性探测法）；写出查找算法，计算在等概率情况下查找成功的平均查找长度。

（15）
5.设有关键码序列10,20,35,40,44,51,65,70,85,91,93,95。

试试着写出冒泡排序，快速排序，直接插入排序，希尔排序。

(15分)
考试科目：数据结构共4 页，第3 页
考试科目：数据结构共 4 页，第 4 页。

数据结构第3章答案(已核)数据结构第3章答案(已核)数据结构是计算机科学中非常重要的一门课程，它研究如何组织和存储数据，以便于高效地访问和处理。

在第3章中，我们学习了一些与树相关的重要概念和算法。

本文将对该章节的内容进行总结和解答。

一、树(Tree)树是一种非线性的数据结构，它由一组节点（Node）和一组连接这些节点的边（Edge）组成。

树的一个节点被称为根节点，它没有父节点；其他节点可以有一个或多个子节点。

树的每个节点除了根节点外都有且只有一个父节点。

树有许多种类，如二叉树、平衡树等。

二、二叉树(Binary Tree)二叉树是一种特殊的树结构，每个节点最多有两个子节点，分别称为左子节点和右子节点。

在二叉树中，左子树和右子树也是二叉树。

二叉树有许多重要的性质和应用，比如二叉搜索树、平衡二叉树等。

三、二叉搜索树(Binary Search Tree)二叉搜索树是一种特殊的二叉树，它的左子树中的所有节点的值都小于根节点的值，而右子树中的所有节点的值都大于根节点的值。

这个特性使得在二叉搜索树中进行插入、删除和查找操作非常高效。

四、平衡二叉树(AVL Tree)平衡二叉树也是一种特殊的二叉搜索树，它的左子树和右子树的高度差不超过1。

通过对插入和删除操作进行树的旋转，可以保持平衡二叉树的平衡性，使得操作的时间复杂度保持在O(log n)。

五、堆(Heap)堆是一种特殊的树结构，它可以分为最大堆和最小堆。

最大堆中，父节点的值大于等于子节点的值；最小堆中，父节点的值小于等于子节点的值。

堆常用于实现优先队列等数据结构，有助于高效地找出最大或最小元素。

六、哈夫曼树(Huffman Tree)哈夫曼树是一种特殊的二叉树，用于实现哈夫曼编码。

在哈夫曼树中，频率较高的字符具有较短的编码，而频率较低的字符具有较长的编码。

哈夫曼树常用于数据压缩领域，可以有效地减少数据的存储空间。

七、图(Graph)图是一种复杂的数据结构，它由节点和连接节点的边组成。

奥鹏17春川农《数据结构（本科）》16秋在线作业一、单选题（共20 道试题，共100 分。

）1. 假设一个有n个顶点和e条弧的有向图用邻接表表示,则删除与某个顶点vi相关的所有弧的时间复杂度是（)A. O(n)B. O(e)C. O(n+e)D. O(n×e)正确答案：2. 线性表是一个具有n个（）的有限序列。

A. 表元素B. 字符C. 数据元素D. 数据项正确答案：3. 依次在初始为空的队列中插入元素X，Y，Z，W以后，紧接着作了两次删除操作，此时的队头元素是（)A. XB. YC. ZD. W正确答案：4. n个顶点的有向完全图中含有向边的数目最多为（)A. n-1B. nC. n(n-1)/2D. n(n-1)正确答案：5. 与数据元素本身的形式、内容、相对位置、个数无关的是数据的( )A. 存储结构B. 逻辑结构C. 算法D. 操作正确答案：6. 对有14个数据元素的有序表R[14]进行折半搜索，搜索到R[3]的关键码等于给定值，此时元素比较顺序依次为( )A. R[0]，R[1]，R[2]，R[3]B. R[0]，R[13]，R[2]，R[3]C. R[6]，R[2]，R[4]，R[3]D. R[6]，R[4]，R[2]，R[3]正确答案：7. 右图中的拓扑序列为（)A. C1，C2，C6，C7，C5，C4，C3B. C1，C2，C6，C3，C4，C5，C7C. C1，C4，C2，C3，C5，C6，C7D. C5，C7，C4，C1，C2，C6，C3正确答案：8. 线性链表不具有的特点是( )A. 随机访问B. 不必事先估计所需存储空间大小C. 插入与删除时不必移动元素D. 所需空间与线性表长度成正比正确答案：9. 设串sl=″Data Structures with Java″,s2=″it″，则子串定位函数index(s1,s2)的值为( )A. 15B. 16C. 17D. 18正确答案：10. 一个二叉树按顺序方式存储在如下的一个维数组中,0 1 2 3 4 5 6 7 8 9 10 11 12 13 14A BC D E F G H I J则结点E在二叉树的第（）层。

大工17春《公司金融》在线作业1一、单选题（共10 道试题，共50 分。

）V1. 财务管理的目标是使股东财富最大化，反映这一目标的最佳指标是（C）。

A. 每股盈余B. 税后净利润C. 股票市价D. 留存收益满分：5 分2. 美国在线收购时代华纳是典型的（D）。

A. 杠杆收购B. 横向收购C. 混合收购D. 纵向收购满分：5 分3. 复利现值系数是(C)。

A. (F/P，i，n)B. (F/A，i，n)C. (P/F，i，n)D. (A/F，i，n) 满分：5 分4. 现有两个投资项目甲和乙，经过计算甲、乙方案的期望值分别为5%、10%，标准离差分别为10%、19%，那么（B）。

A. 甲项目的风险程度与乙项目的风险程度相同B. 甲项目的风险程度高于乙项目的风险程度C. 甲项目的风险程度低于乙项目的风险程度D. 不能比较两个项目的风险程度满分：5 分5. 若某只股票的β系数为1，则下列表述正确的是（A）。

A. 该股票的市场风险等于全部市场股票的风险B. 该股票的市场风险小于全部市场股票的风险C. 该股票的市场风险大于全部市场股票的风险D. 该股票的市场风险与全部市场股票的风险无关满分：5 分6. “不要把所有的鸡蛋放到一个篮子里”是哪一条公司理财的基本原则(C)。

A. 增量现金流量原则B. 货币时间价值原则C. 风险分散原则D. 市场效率原则满分：5 分7. 现代公司金融管理的目标是以(A)最大化为标志的。

A. 公司价值B. 社会责任C. 税后利润D. 资本利润率满分：5 分8. 影响货币时间价值大小的因素包括（A）。

A. 资金额B. 复利C. 单利D. 汇率满分：5 分9. 标准差测度的是（A）。

A. 总体风险B. 不可分散的风险C. 非系统风险D. 系统风险满分：5 分10. 有限合伙制企业属于（B）。

A. 个体业主制企业B. 合伙制企业C. 公司制企业D. 公司满分：5 分二、多选题（共 5 道试题，共30 分。

数据结构部分课后习题答案(1-3)第一章1.1数据的逻辑结构是从具体问题中抽象出来的数学模型，体现了事物的组成和事物之间的逻辑关系。

数据的存储结构主要用来解决各种逻辑结构在计算机中物理存储表示的问题。

1.2事前分析和事后统计事前分析：优点，程序不必运行，所得结果只依赖于算法本身缺点，不够精确事后统计：优点，精确缺点，必须运行程序，所得结果依赖于硬件、环境等因素1.3void func(int n){int i=1,k=100;while(i<n){k++;i+=2;}}考虑赋值、运算操作执行的次数第3行赋值2次第6行赋值执行n次，加法执行n次所以，总共2n+2次操作，算法复杂度为O(n)1.4y=y+i*j执行次数：1.5第二章2.9内存中一片连续空间（不妨假设地址从1到m）提供给两个栈S1和S2使用，怎样分配这部分存储空间，使得对任一个栈，仅当这部分空间全满时才发生上溢。

答：S1和S2共享内存中一片连续空间（地址1到m），可以将S1和S2的栈底设在两端，两栈顶向共享空间的中心延伸，仅当两栈顶指针相邻（两栈顶指针值之差的绝对值等于1）时，判断为栈满，当一个栈顶指针为0，另一个栈顶指针m+1时为两栈均空。

2.10线性表是数据项组成的一种有限且有序的序列，各元素之间呈线性关系。

从逻辑结构来说，栈和队列与线性表相同，都是典型的线性结构。

与线性表不同的是，栈和队列的操作特殊，受到一定的限制，仅允许在线性表的一端或两端进行。

栈是限定仅在一端进行插入删除的线性表，无论插入、删除还是读取都在一端进行，按后进先出的原则。

队列的元素只能从一端插入，从另一端删除，按先进先出的原则进行数据的存取。

2.11共有132种合法序列。

235641序列可以。

154623序列不可以。

对于每一个数来说，必须进栈一次、出栈一次。

我们把进栈设为状态‘1’，出栈设为状态‘0’。

n个数的所有状态对应n个1和n个0组成的2n位二进制数。

一、单项选择题（共 10 道试题，共 50 分。

） V 1. 最短途径的生成算法可用（）算法。

A. 普里姆B. 迪杰斯特拉C. 克鲁斯卡尔D. 哈夫曼2. 设一组初始记录序列为(5，2，6，3，8)，以5为基准进行一趟快速排序的结果为（）。

A. 2，3，5，8，6B. 3，2，5，6，8C. 3，2，5，8，6D. 2，3，6，5，83. 线性表中采纳折半查找法查找元素，该线性表应该有（）特点。

A. 元素按值有序，且采纳链式存储结构B. 元素按值有序，且采纳顺序存储结构C. 采纳顺序存储结构D. 元素按值有序4. 在1000个无序的元素用最快的速度挑选出其中前10个最大的元素，最好选用（）排序法。

A. 冒泡排序B. 快速排序C. 基数排序D. 堆排序5. 有n个极点和e条边的有向图进行拓扑排序时，总的计算时刻为（）。

A. O (nlog2e)B. O (n+e)C. O (en )D. O ( elog2n)6. 对一组数据（46,79,56,38,40,84）采纳快速排序的方式，以第一个记录为基准取得的一次划分结果为（）。

A. 38,40,46,56,79,84B. 40,38,46,84,56,79C. 40,38,46,56,79,84D. 40,38,46,79,56,847. 一个有序表中的元素为(12，17，24，35，47，50，62)，那么在其中利用二分法查找值为24的元素需要通过（）次比较。

A. 1B. 2C. 3D. 48. 有n个极点e条边的无向图G中，其对应的邻接表中的表头结点和表结点的个数别离为（）。

A. n和2eB. 2n和eC. e和nD. n和e9. 用顺序查找法在具有n个结点的线性表中查找一个结点的时刻复杂度为（）。

A. O(log2n^2)B. O(nlog2n)C. O(n)D. O(log2n)10. 下面四种排序法中（）排序法是不稳固性排序法。

A. 插入B. 冒泡C. 堆排序D. 二路归并二、判定题（共 10 道试题，共 50 分。

大工18春《数据结构》在线作业3
试卷总分:100 得分:100
一、判断题 (共 10 道试题,共 50 分)
1.散列文件中存放一组记录的存储单位称为桶。

A.对
B.错
正确答案:A
2.散列方法的查找性能用平均查找长度ASL来衡量。

A.对
B.错
正确答案:A
3.二分查找对线性表的存储结构无任何要求。

A.对
B.错
正确答案:B
4.折半查找只能在有序的顺序表上进行而不能在有序链表上进行。

A.对
B.错
正确答案:A
5.快速排序算法是一种不稳定的算法。

A.对
B.错
正确答案:A
6.直接选择排序属于选择类排序,是一种稳定的排序方法。

A.对
B.错
正确答案:B
7.对于一个堆,按二叉树层次进行遍历可以得到一个有序序列。

A.对
B.错
正确答案:B。

国家开放大学电大《数据结构》网络课形考任务3作业及答案形考任务3一、单项选择题（每小题2分，共38分）题目1假定一棵二叉树中，双分支结点数为15,单分支结点数为30,则叶子结点数为（）o选择一项：A. 47B. 16C. 17D. 15题目2二叉树第k层上最多有（）个结点。

选择一项：A. 2k-lB. 2k-lC. 2k-lD. 2k题目3将含有150个结点的完全二叉树从根这一层开始，每一层从左到右依次对结点进行编号，根结点的编号为1,则编号为69的结点的双亲结点的编号为（）o选择一项：A. 36B. 35C. 34D. 33题目4如果将给定的一组数据作为叶子数值，所构造出的二叉树的带权路径长度最小，则该树称为（）o选择一项：A. 二叉树B. 哈夫曼树C. 完全二叉树D. 平衡二叉树在一棵度具有5层的满二叉树中结点总数为（）o选择一项：A. 16B. 32C. 31D. 33题目6一棵完全二叉树共有6层，且第6层上有6个结点，该树共有（）个结点。

选择一项：A. 31B. 37C. 38D. 72题目7利用3、6、8、12这四个值作为叶子结点的权，生成一棵哈夫曼树，该树中所有叶子结点中的最长带权路径长度为（）。

选择一项：A. 18B. 16C. 30D. 12题目8在一棵树中，（）没有前驱结点。

选择一项：A. 树根结点B. 叶结点C. 空结点D. 分支结点题目9设一棵采用链式存储的二叉树，除叶结点外每个结点度数都为2,该树结点中共有20个指针域为空，则该树有（）个叶结点。

选择一项：C. 21D. 22题目10在一个图G中，所有顶点的度数之和等于所有边数之和的（）倍。

选择一项：A. 2B. 1C. 4D. 1/2题目11邻接表是图的一种（）o选择一项：A. 链式存储结构B. 顺序存储结构C. 散列存储结构D. 索引存储结构题目12图的深度优先遍历算法类似于二叉树的（）遍历。

选择一项：A. 先序B. 后序C. 层次D. 中序题目13已知下图所示的一个图，若从顶点VI出发，按深度优先搜索法进行遍历，则可能得到的一种顶点序列为（）。