山大网络教育《数据结构》(-C-卷)

电子科技大学网络教育-数据结构（专科）试题及答案（7）一、单选，共30题/每题2.5分/共75.0分：1、算法分析的两个主要方面是（）。

A、正确性和简单性B、数据复杂性和程序复杂性C、可读性和文档性D、空间复杂度和时间复杂度得分：2.52、算法原则上都是能够由机器或人完成的。

整个算法好像是一个解决问题的“工作序列”，其中的每一步都是我们力所能及的一个动作。

这是算法的（）。

A、正确性B、可行性C、确定性D、有穷性得分：2.53、计算机中的算法指的是解决某一个问题的有限运算序列，它必须具备输入、输出、（）等5个特性。

A、可执行性、可移植性和可扩充性B、确定性、有穷性和稳定性C、易读性、稳定性和确定性D、可执行性、有穷性和确定性得分：2.54、无向图顶点v的度为关联于该顶点（）的数目.A、顶点B、序号X、边∆、下标得分：2.55、将递归算法转换成对应的非递归算法时，通常需要使用下列哪种数据结构来保存中间结果（）。

A、树B、队列X、链表∆、栈得分：2.56、某二叉树的中序序列为ABCDEFG，后序序列为BDCAFGE，则其左子树中结点数目为（）。

A、3B、5X、2∆、4得分：2.57、已知一个有向图的邻接矩阵表示，要删除所有从第i个结点发出的边，应（）。

A、将邻接矩阵的第ι行删除B、将邻接矩阵的第ι列元素全部置为0X、将邻接矩阵的第ι列删除∆、将邻接矩阵的第ι行元素全部置为0得分：2.58、带头结点的单链表head为空的判定条件是（）。

A、ηεαδ!=NYΛΛB、ηεαδ->νεξτ!=NYΛΛX、ηεαδ->νεξτ==NYΛΛ∆、ηεαδ==NYΛΛ得分：0.09、生成树的构造方法有（）。

A、深度优先B、深度优先和广度优先X、无后继的顶点优先∆、无前驱的顶点优先得分：2.510、下面程序段的时间复杂度是（）。

for(i=0;i<m;i++)for(j=0;j<n;j++)a[i][j]=i*j;A、O(m2)B、O(m*n)C、O(m+n)D、O(n2)得分：0.011、在一棵具有5层的满二叉树中结点总数为（）。

一、填空题：（每小题2分，共10分）1. 设有数据结构（D，R），其中D 是数据元素的有限集，R 是的有限集。

2. 深度为k 的二叉树其结点数至多有个。

3. 栈是一种特殊的线性表，它允许在表的一端进行操作。

4. 通常象交通、道路问题的数学模型是一种称为的数据结构。

5. 哈希表是一种查找表，可以根据哈希函数直接获得。

二、单项选择题：（每小题2分，共10分）对于下列各题，在备选答案中选出一个正确的，并将其编号填在“”位置上。

1. 若线性表最常用的操作是存取第i 个元素及其前驱元素的值，则采用存储方式最节省运算时间。

A. 单链表B. 双链表C. 单循环链表D. 顺序表2. 下列排序算法中，算法在进行一趟相应的排序处理结束后不一定能选出一个元素放到其最终位置上。

A. 直选择排序B. 冒泡排序C. 归并排序D. 堆排序3. 队列的操作原则是。

A. 先进后出B. 先进先出C. 只能进行插入D. 只能进行删除4. 在具有n 个结点的二叉链表中，非空的链域个数为。

A. n-1B. nC. n+1D. 不确定5. 对具有n 个元素的有序查找表采用折半查找算法查找一个键值，其最坏比较次数的数量级为。

A. O(log2n)B. O(n)C. O(nlog2n)D. O(n2)三、判断题：（每小题2分，共10分）判断下列各题是否正确，若正确，在题后的括号内填“T”，否则填“F”。

1. 在栈为空的情况下不能作出栈处理，否则，将产生下溢出。

（）2. 如果有向图G=(V, E) 的拓扑序列唯一，则图中必定仅有一个顶点的入度为0、一个顶点的出度为0。

（）3. 在大根堆中，必定满足每个结点的键值大于其左右子树中所有结点的键值。

（）4. 在采用线性探测法处理冲突的散列表中所有同义词在表中相邻。

（）5. 在索引顺序表中，对索引表既可采用顺序查找，也可采用二分查找。

（）四、解答下列各题：（每题10分，共40分）1. 已知线性表L 采用带头结点的的单向循环链表表示，试给出它的存储结构类型描述及相应的示意图。

数据结构（第4版）习题及实验参考答案数据结构复习资料完整版（c语言版）数据结构基础及深入及考试习题及实验参考答案见附录结论1、数据的逻辑结构是指数据元素之间的逻辑关系。

即从逻辑关系上描述数据，它与数据的存储无关，是独立于计算机的。

2、数据的物理结构亦称存储结构，是数据的逻辑结构在计算机存储器内的表示（或映像）。

它依赖于计算机。

存储结构可分为4大类：顺序、链式、索引、散列3、抽象数据类型：由用户定义，用以表示应用问题的数据模型。

它由基本的数据类型构成，并包括一组相关的服务（或称操作）。

它与数据类型实质上是一个概念，但其特征是使用与实现分离，实行封装和信息隐蔽（独立于计算机）。

4、算法：是对特定问题求解步骤的一种描述，它是指令的有限序列，是一系列输入转换为输出的计算步骤。

5、在数据结构中，从逻辑上可以把数据结构分成（C）A、动态结构和表态结构B、紧凑结构和非紧凑结构C、线性结构和非线性结构D、内部结构和外部结构6、算法的时间复杂度取决于（A）A、问题的规模B、待处理数据的初态C、问题的规模和待处理数据的初态线性表1、线性表的存储结构包括顺序存储结构和链式存储结构两种。

2、表长为n的顺序存储的线性表，当在任何位置上插入或删除一个元素的概率相等时，插入一个元素所需移动元素的平均次数为（E），删除一个元素需要移动的元素的个数为（A）。

A、(n-1)/2B、nC、n+1D、n-1E、n/2F、(n+1)/2G、(n-2)/23、“线性表的逻辑顺序与存储顺序总是一致的。

”这个结论是（B）A、正确的B、错误的C、不一定，与具体的结构有关4、线性表采用链式存储结构时，要求内存中可用存储单元的地址（D）A、必须是连续的B、部分地址必须是连续的C一定是不连续的D连续或不连续都可以5、带头结点的单链表为空的判定条件是（B）A、head==NULLB、head->ne某t==NULLC、head->ne某t=headD、head!=NULL6、不带头结点的单链表head为空的判定条件是（A）A、head==NULLB、head->ne某t==NULLC、head->ne某t=headD、head!=NULL7、非空的循环单链表head的尾结点P满足（C）A、p->ne某t==NULLB、p==NULLC、p->ne某t==headD、p==head8、在一个具有n个结点的有序单链表中插入一个新结点并仍然有序的时间复杂度是（B）A、O(1)B、O(n)C、O(n2)D、O(nlog2n)数据结构(第4版）习题及实验参考答案9、在一个单链表中，若删除p所指结点的后继结点，则执行（A）A、p->ne某t=p->ne某t->ne某t;B、p=p->ne某t;p->ne某t=p->ne某t->ne某t;C、p->ne某t=p->ne某t;D、p=p->ne某t->ne某t;10、在一个单链表中，若在p所指结点之后插入所指结点，则执行（B）A、->ne某t=p;p->ne某t=;B、->ne某t=p->ne某t;p->ne某t=;C、->ne某t=p->ne某t;p=;D、p->ne某t=;->ne某t=p;11、在一个单链表中，已知q是p的前趋结点，若在q和p之间插入结点，则执行（C）A、->ne某t=p->ne某t;p->ne某t=;B、p->ne某t=->ne某t;->ne某t=p;C、q->ne某t=;->ne某t=p;D、p->ne某t=;->ne某t=q;12、在线性结构中，第一个结点没有前趋结点，其余每个结点有且只有1个前趋结点。

《C语言程序设计》模拟卷C卷题号一二三四总分得分评卷人一、选择题1．以下说法中正确的是（ C ）。

A．C语言程序总是从第一个函数开始执行B．C语言程序中，要调用的函数必须在main()函数中定义C．C语言程序总是从main( )函数开始执行D．C语言程序中的main( )函数必须放在程序的开始部分2．下列为字符常量的是（ C ）。

A．“a”B. ...ab‟C....\n‟D. (084)3．在C语言中,下面字符串能用作变量名的是（ D ）。

A. a+bB. autoC. 2-andD. a24．在C语言中运算对象必须是整型的运算符是（A）。

A. %B. /C. = =D. <=5．若有以下定义：int x=10,y=3,z; 则语句:printf(“%d\n”,z=(x%y,x/y));的输出结果为( D )。

A. 1B. 0C. 2D. 36．表达式（A）的值是整数类型。

A.15/2B. 15/2+2.0C.25/5.0D.0.5*107．若double x=2，y；则执行y=x+3/2；后，y的值是（B ）。

A. 3.500000B. 3.000000C. 2.000000D. 38．C语言程序的基本单位是（ B ）。

A.程序行B.语句C.函数D.字符9．设int类型的数据长度为2字节，则int类型数据的取值范围是（B ）。

A. 0～255B. -32768～32767C. -256～255D. 0～6553510．语句int (*p)( )的含义是（ C ）。

A. p是一个指向一维数组的指针变量B.p是指针变量，它指向一个整型数据的指针C.p是一个指向函数的指针，该函数的返回值为整型D. 以上答案都不对11．下面程序的输出结果是（A）。

main（）{ int x =10，y =10；printf（“%d，%d\n”，x--，y--）；}A. 10，10B. 9，9C. 9，10D. 10，912．（ B ）是C语言的标准函数名。

大学计算机《数据结构》试卷及答案一、选择题(30分)1．设一维数组中有n个数组元素，则读取第i个数组元素的平均时间复杂度为（）。

(A) O(n) (B) O(nlog2n) (C) O(1) (D) O(n2)2．设一棵二叉树的深度为k，则该二叉树中最多有（）个结点。

(A) 2k-1 (B) 2k(C) 2k-1(D) 2k-13．设某无向图中有n个顶点e条边，则该无向图中所有顶点的入度之和为（）。

(A) n (B) e (C) 2n (D) 2e4．在二叉排序树中插入一个结点的时间复杂度为（）。

(A) O(1) (B) O(n) (C) O(log2n) (D) O(n2)5．设某有向图的邻接表中有n个表头结点和m个表结点，则该图中有（）条有向边。

(A) n (B) n-1 (C) m (D) m-16．设一组初始记录关键字序列为(345，253，674，924，627)，则用基数排序需要进行（）趟的分配和回收才能使得初始关键字序列变成有序序列。

(A) 3 (B) 4 (C) 5 (D) 87．设用链表作为栈的存储结构则退栈操作（）。

(A) 必须判别栈是否为满(B) 必须判别栈是否为空(C) 判别栈元素的类型(D) 对栈不作任何判别8．下列四种排序中（）的空间复杂度最大。

(A) 快速排序(B) 冒泡排序(C) 希尔排序(D) 堆9．设某二叉树中度数为0的结点数为N0，度数为1的结点数为N l，度数为2的结点数为N2，则下列等式成立的是（）。

(A) N0=N1+1 (B) N0=N l+N2(C) N0=N2+1 (D) N0=2N1+l10.设有序顺序表中有n个数据元素，则利用二分查找法查找数据元素X的最多比较次数不超过（）。

(A) log2n+1 (B) log2n-1 (C) log2n (D) log2(n+1)二、填空题(42分)1．设有n个无序的记录关键字，则直接插入排序的时间复杂度为________，快速排序的平均时间复杂度为_________。

数据结构试卷及参考答案（五）一、选择题(20分)1．数据的最小单位是（）。

(A)数据项(B)数据类型(C)数据元素(D)数据变量2．设一组初始记录关键字序列为(50，40，95，20，15，70，60，45)，则以增量d=4的一趟希尔排序结束后前4条记录关键字为（）。

(A)40，50，20，95(B)15，40，60，20(C)15，20，40，45(D)45，40，15，203．设一组初始记录关键字序列为(25，50，15，35，80，85，20，40，36，70)，其中含有5个长度为2的有序子表，则用归并排序的方法对该记录关键字序列进行一趟归并后的结果为（）。

(A)15，25，35，50，20，40，80，85，36，70(B)15，25，35，50，80，20，85，40，70，36(C)15，25，35，50，80，85，20，36，40，70(D)15，25，35，50，80，20，36，40，70，854．函数substr(“DATASTRUCTURE”，5，9)的返回值为（）。

(A)“STRUCTURE”(B)“DATA”(C)“ASTRUCTUR”(D)“DATASTRUCTURE”5．设一个有序的单链表中有n 个结点，现要求插入一个新结点后使得单链表仍然保持有序，则该操作的时间复杂度为（）。

(A)O(log 2n)(B)O(1)(C)O(n 2)(D)O(n)6．设一棵m 叉树中度数为0的结点数为N 0，度数为1的结点数为N l ，……，度数为m 的结点数为Nm，则N 0=（）。

(A)N l +N 2+……+Nm (B)l+N 2+2N 3+3N 4+……+(m-1)Nm(C)N 2+2N 3+3N 4+……+(m-1)Nm (D)2N l +3N 2+……+(m+1)Nm7．设有序表中有1000个元素，则用二分查找查找元素X 最多需要比较（）次。

(A)25(B)10(C)7(D)18．设连通图G 中的边集E={(a ，b)，(a ，e)，(a ，c)，(b ，e)，(e ，d)，(d ，f)，(f ，c)}，则从顶点a 出发可以得到一种深度优先遍历的顶点序列为（）。

概率统计模拟题一、填空1、设A 、B 是二随机事件，则A 、B 同时发生的事件可表示为 AB 。

2、n 重贝努利试验中，事件A 出现k 次的概率为。

3、设A 、B 是二随机事件，如果等式 成立，则称A 、B 为相互独立的随机事件。

4、设f(x)≥0，当f(x)满足条件时，则称f(x)为某一随机变量X 的密度函数。

5、如果随机变量X~N(0，2)，则X 的分布函数F(x)为。

6、设随机变量X 服从参数为 λ 的指数分布，则E(X)= ；D(X)=。

二、设随机变量X 的概率分布为X 0 1 2P 321p - 3p 3p分别求()E X 、()D X ；并问当?p = 时，使得max{()}D X 达到最大。

参考答案： 解：（1） ()1233p pE X p =⨯+⨯= 因为2225()12333p p p E X =⨯+⨯=，所以2225()()3p D X EX EX p =-=-因为25()53203pd p p dp -=-=，解之得 56p =，又因为2225()320pd p dp -=-<，所以()D X 在56p =处取得最大值。

三、 设随机变量X 的分布函数为⎪⎩⎪⎨⎧≥<≤<=111000)(2x x ax x x F试求（１）常数a ；（２）P{0.3<X<0.7}；（３）X 的概率密度函数f(x)。

参考答案： 解：（1）211lim lim11x x ax a -+→→=== 得 1a =（2）P{0.3<X<0.7} = F(0.7) − F(0.3) = 0.72 − 0.3 2= 0.40(3) 201()00, 1x x f x x or x <<⎧=⎨≤≥⎩ 四、设(X 1,X 2,•••,X n )来自正态总体X 的一个简单随机样本，X 的密度函数为（θ>0）试求θ的极大似然估计量。

参考答案： 解：设1,,n X X 为来自总体的一个样本，则似然函数为1111()()()nni i i i L x x θθθθθ--====∏∏取似然函数1ln ()ln (1)ln ni i L n x θθθ==+-∑求导得1ln ()ln 0ni i d L n x d θθθ==+=∑ 解得1ln nii nxθ==-∑五、设随机变量Y ~ N(8，0.52)，求P{ | Y − 8 | < 1 } 及P{ Y < 10 }。

第1章绪论5．选择题：CCBDCA6．试分析下面各程序段的时间复杂度。

（1)O（1）（2）O(m＊n）（3）O（n2）（4)O（log3n）（5)因为x++共执行了n—1+n—2+……＋1= n(n—1)/2，所以执行时间为O(n2)（6）O(n）第2章线性表1．选择题babadbcabdcddac2．算法设计题(6）设计一个算法，通过一趟遍历在单链表中确定值最大的结点。

ElemType Max （LinkList L ）｛if(L—〉next==NULL) return NULL；pmax=L-〉next；//假定第一个结点中数据具有最大值p=L-〉next—>next；while(p ！= NULL ){//如果下一个结点存在if（p->data > pmax—>data) pmax=p；p=p->next；｝return pmax-〉data;（7)设计一个算法，通过遍历一趟，将链表中所有结点的链接方向逆转，仍利用原表的存储空间.void inverse(LinkList ＆L) ｛// 逆置带头结点的单链表Lp=L-〉next；L->next=NULL；while （p）｛q=p—>next；// q指向＊p的后继p->next=L—>next;L—>next=p; // *p插入在头结点之后p = q;｝}（10)已知长度为n的线性表A采用顺序存储结构,请写一时间复杂度为O(n)、空间复杂度为O（1）的算法，该算法删除线性表中所有值为item的数据元素.［题目分析］在顺序存储的线性表上删除元素,通常要涉及到一系列元素的移动（删第i个元素，第i+1至第n个元素要依次前移)。

本题要求删除线性表中所有值为item的数据元素，并未要求元素间的相对位置不变。

因此可以考虑设头尾两个指针（i=1，j=n）,从两端向中间移动，凡遇到值item的数据元素时，直接将右端元素左移至值为item的数据元素位置。

第1章绪论5．选择题：CCBDCA6．试分析下面各程序段的时间复杂度。

（1）O（1）（2）O（m*n）（3）O（n2）（4）O（log3n）（5）因为x++共执行了n-1+n-2+……＋1= n(n-1)/2，所以执行时间为O（n2）（6）O(n)第2章线性表1．选择题babadbcabdcddac2．算法设计题（6）设计一个算法，通过一趟遍历在单链表中确定值最大的结点。

ElemType Max (LinkList L ){if(L->next==NULL) return NULL;pmax=L->next; //假定第一个结点中数据具有最大值p=L->next->next;while(p != NULL ){//如果下一个结点存在if(p->data > pmax->data) pmax=p;p=p->next;}return pmax->data;（7）设计一个算法，通过遍历一趟，将链表中所有结点的链接方向逆转，仍利用原表的存储空间。

void inverse(LinkList &L) {// 逆置带头结点的单链表 Lp=L->next; L->next=NULL;while ( p) {q=p->next; // q指向*p的后继p->next=L->next;L->next=p; // *p插入在头结点之后p = q;}}（10）已知长度为n的线性表A采用顺序存储结构，请写一时间复杂度为O(n)、空间复杂度为O(1)的算法，该算法删除线性表中所有值为item的数据元素。

[题目分析] 在顺序存储的线性表上删除元素，通常要涉及到一系列元素的移动（删第i个元素，第i+1至第n个元素要依次前移）。

本题要求删除线性表中所有值为item的数据元素，并未要求元素间的相对位置不变。

因此可以考虑设头尾两个指针（i=1，j=n），从两端向中间移动，凡遇到值item的数据元素时，直接将右端元素左移至值为item的数据元素位置。

《数据结构与算法》复习题应用简答题.1．有下列几种用二元组表示的数据结构，画出它们分别对应的逻辑图形表示，并指出它们分别属于何种结构。

(1）A ＝｛D，R｝,其中：D＝｛a，b，c，d，e，f，g，h｝,R ＝｛r｝，r ＝｛<a,b>，<b,c>，〈c，d〉,〈d，e>，〈e,f〉，<f,g>，<g，h〉｝（2）B ＝｛D,R｝，其中：D＝{a，b，c，d,e，f，g，h｝，R ＝｛r｝，r ＝｛<d，b>，〈d，g〉,<d，a〉,<b,c>，<g，e>,<g,h〉，〈e,f〉｝(3)C ＝｛D,R｝，其中：D＝｛1，2,3，4,5，6｝，R ＝｛r｝，r ＝｛（1，2），（2,3）,（2，4），(3，4），（3，5），（3，6），（4，5),（4，6）｝2．简述顺序表和链表存储方式的特点。

答:顺序表的优点是可以随机访问数据元素，缺点是大小固定，不利于增减结点（增减结点操作需要移动元素）。

链表的优点是采用指针方式增减结点，非常方便（只需改变指针指向，不移动结点)。

其缺点是不能进行随机访问，只能顺序访问。

另外，每个结点上增加指针域，造出额外存储空间增大.3．对链表设置头结点的作用是什么?（至少说出两条好处）答：其好处有：(1）对带头结点的链表,在表的任何结点之前插入结点或删除表中任何结点，所要做的都是修改前一个结点的指针域,因为任何元素结点都有前驱结点（若链表没有头结点，则首元素结点没有前驱结点，在其前插入结点和删除该结点时操作复杂些）。

（2）对带头结点的链表，表头指针是指向头结点的非空指针，因此空表与非空表的处理是一样的。

4．对于一个栈,给出输入项A ，B,C 。

如果输入项序列由A ，B,C 组成,试给出全部可能的输出序列。

5．设有4个元素1、2、3、4依次进栈,而栈的操作可随时进行（进出栈可任意交错进行，但要保证进栈次序不破坏1、2、3、4的相对次序），请写出所有不可能的出栈次序和所有可能的出栈次序.6．现有稀疏矩阵A 如图所示，要求画出三元组表示法和十字链表表示法：⎥⎥⎥⎥⎥⎥⎥⎥⎦⎤⎢⎢⎢⎢⎢⎢⎢⎢⎣⎡--000280000000910000000060000003130150220157．设4维数组的4个下标的范围分别为［-1，0］,[1,2],［1,3],[-2，-1]，请分别按行序和列序列出各元素。