《数据结构》期末考A、B卷(本科)

《数据结构》期末考试试卷试题及答案第一部分：选择题（每题2分，共20分）1. 下面哪个数据结构是线性结构？A. 树B. 图C. 队列D. 网络流2. 下面哪个数据结构用于实现广度优先搜索算法？A. 栈B. 队列C. 散列表D. 堆3. 下面哪个数据结构用于实现深度优先搜索算法？A. 栈B. 队列C. 散列表D. 堆4. 下面哪个数据结构用于实现快速排序算法？A. 栈B. 队列C. 散列表D. 堆5. 下面哪个数据结构用于实现优先队列？A. 栈B. 队列C. 散列表D. 堆6. 下面哪个数据结构用于实现哈希表？A. 栈B. 队列C. 散列表D. 堆7. 下面哪个数据结构用于实现最小树算法？A. 栈B. 队列C. 散列表D. 堆8. 下面哪个数据结构用于实现拓扑排序算法？A. 栈B. 队列C. 散列表D. 堆9. 下面哪个数据结构用于实现最短路径算法？A. 栈B. 队列C. 散列表D. 堆10. 下面哪个数据结构用于实现并查集算法？A. 栈B. 队列C. 散列表D. 堆第二部分：填空题（每题2分，共20分）1. 链表是一种______数据结构。

2. 二叉树的节点最多有______个子节点。

3. 堆是一种特殊的______。

4. 散列表的查找效率取决于______。

5. 图的遍历算法包括______和______。

6. 快速排序算法的平均时间复杂度为______。

7. 哈希表中的冲突解决方法有______和______。

8. 最小树算法包括______和______。

9. 最短路径算法包括______和______。

10. 并查集算法用于解决______问题。

第三部分：简答题（每题10分，共50分）1. 请简述栈和队列的区别。

2. 请简述二叉搜索树的特点。

3. 请简述哈希表的原理。

4. 请简述图的深度优先搜索算法。

5. 请简述最小树算法的原理。

第四部分：编程题（每题20分，共50分）1. 编写一个函数，实现链表的插入操作。

《数据结构》试题（100分）（供2005级信息管理与信息系统本科专业使用）学号： 姓名： 座号： 系别： 年级： 专业：总分合计人： 复核人：说明：本试卷分为两部分，第I 卷（选择题和判断题）必须在“答题卡”上按规定要求填、涂；第II 卷直接在试卷上作答。

不按规定答题、填涂，一律无效。

第I 卷一、试题类型：单项选择题（每小题2分，共40分） （类型说明：在每小题列出的四个选项中只有一个选项是符合题目要求的，请选出正确选项并在“答题卡”的相应位置上涂黑。

多涂、少涂、错误均无分。

）1. 算法分析的两个主要方面是：（ ）（A) 空间复杂性和时间复杂性 （B) 正确性和简明性 （C) 可读性和文档性 （D) 数据复杂性和程序复杂性2. 计算机算法指的是： （ ）（A) 计算方法 （B) 排序方法 （C) 解决问题的有限运算序列 （D) 调度方法 3． 数据在计算机存储器内表示时，物理地址与逻辑地址相同并且是连续的，称为：（ ）（A ）存储结构 （B ）逻辑结构 （C ）顺序存储结构 （D ）链式存储结构 4.一个向量第一个元素的存储地址是100，每个元素的长度为2，则第5个元素的地址是 。

（ ）（A ）110 （B ）108 （C ）100 （D ）1205. 链接存储的存储结构所占存储空间： （ ）（A ）分两部分，一部分存放结点值，另一部分存放表示结点间关系的指针 （B ）只有一部分，存放结点值（C ） 只有一部分，存储表示结点间关系的指针（D ） 分两部分，一部分存放结点值，另一部分存放结点所占单元数 6. 线性表若采用链式存储结构时，要求内存中可用存储单元的地址: （ ）（A ）必须是连续的 （B ）部分地址必须是连续的 （C ）一定是不连续的 （D ）连续或不连续都可以7. 栈中元素的进出原则是：（）（Ａ）先进先出（Ｂ）后进先出（Ｃ）栈空则进（Ｄ）栈满则出8. 若已知一个栈的入栈序列是1，2，3，…，n，其输出序列为p1，p2，p3，…，pn，若p1=n，则pi为：（）（Ａ） i （Ｂ） n=i （Ｃ） n-i+1 （Ｄ）不确定9. 串是一种特殊的线性表，其特殊性体现在：（）（Ａ）可以顺序存储（Ｂ）数据元素是一个字符（Ｃ）可以链式存储（Ｄ）数据元素可以是多个字符10. 设串s1=‘ABCDEFG’，s2=‘PQRST’，函数con(x,y)返回x和y串的连接串，subs(s, i, j)返回串s的从序号i开始的j个字符组成的子串，len(s)返回串s的长度，则con(subs(s1, 2, len(s2)), subs(s1, len(s2), 2))的结果串是：（）（Ａ）BCDEF （Ｂ）BCDEFG （Ｃ）BCPQRST （Ｄ）BCDEFEF11. 假设有60行70列的二维数组a[1…60, 1…70]以列序为主序顺序存储，其基地址为10000，每个元素占2个存储单元，那么第32行第58列的元素a[32,58]的存储地址为。

计算机科学与技术、网络工程本科《数据结构》期末考试试卷一、选择题〔单选题，每小题3分，共33分〕1．已知某二叉树的中序、层序序列分别为DBAFCE、FDEBCA，则该二叉树的后序序列为。

A．BCDEAF B．ABDCEF C．DBACEF D．DABECF 2．在11个元素的有序表A[1…11]中进行折半查找〔⎣⎦2/)low+〕，查找元素(highA[11]时，被比较的元素的下标依次是。

A．6，8，10，11 B．6，9，10，11 C．6，7，9，11 D．6，8，9，113．由元素序列〔27，16，75，38，51〕构造平衡二叉树，则首次出现的最小不平衡子树的根〔即离插入结点最近且平衡因子的绝对值为2的结点〕为。

A．27 B．38 C．51 D．754．利用逐点插入法建立序列〔50，72，43，85，75，20，35，45，65，30〕对应的二叉排序树以后，查找元素30要进行次元素间的比较。

A．4 B．5 C．6 D．75．循环链表的主要优点是。

A．不再需要头指针了B．已知某个结点的位置后，很容易找到它的直接前驱结点C．在进行删除后，能保证链表不断开D．从表中任一结点出发都能遍历整个链表6．已知一个线性表〔38，25，74，63，52，48〕，假定采用散列函数h〔key〕=key%7计算散列地址，并散列存储在散列表A[0…6]中，若采用线性探测方法解决冲突，则在该散列表上进行等概率查找时查找成功的平均查找长度为。

A．1．5 B．1．7 C．2．0 D．2．37．由权值为9，2，5，7的四个叶子结点构造一棵哈夫曼树，该树的带权路径长度为。

A．23 B．37 C．44 D．468．在最好和最坏情况下的时间复杂度均为O〔nlogn〕且稳定的排序方法是。

A．基数排序B．快速排序C．堆排序D．归并排序9．无向图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卷）（考试时间：90分钟）一、单项选择题（本大题共15小题，每小题2分，共30分）（每题只有一个选项是正确的,将答案填写在括号内，错选、多选不得分）1.（）是组成数据的基本单位，是一个数据整体中相对独立的单元。

A．数据 B.数据元素 C.数据对象 D.数据结构2.算法计算量的大小称为算法的（）。

据的存3.4.5.6.7.8.A.线性表采用顺序存储，必须占用一片连续的存储单元。

B.线性表采用顺序存储，便于进行插入和删除操作。

C.线性表采用链式存储，不必占用一片连续的存储单元。

D.线性表采用链式存储，便于插入和删除操作。

9.队列操作的原则是（）。

A.后进先出B.先进先出C.只能进行插入D.只能进行删除10.栈中允许进行插入和删除的一端称为（）。

A.栈首B.栈尾C.栈顶D.栈底11．假设以数组A[n]存放循环队列的元素，其首尾指针分别为front和rear，则当前队列中的元素个数为（）。

A．（rear-front+n）%nB.rear-front+1C.(front-rear+n)%nD.(rear-front)%n12.最大容量为n的循环队列，队尾指针是rear，队首指针是front，则队空的判断条件是（）。

13.构。

14.15.12在q3．放了2个字符。

4．广义表（a,b,c,d）的表尾是。

5．一棵深度为k的二叉树，最多有个结点。

6．已知有向图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的拓扑序列是______。

7.有n个顶点的连通图至少有条边。

8.1.（）23.4（）5.6.7.8.9.（）10.采用线性探测法解决冲突问题，所产生的一系列后继散列地址必须大于等于原散列址。

武夷学院期末考试试卷（ 09级计算机科学与技术专业2010 ～2011 学年度第 1 学期） 课程名称 数据结构 A 卷 考试形式 闭卷 考核类型 考试 本试卷共 五 大题，卷面满分100分，答题时间120分钟。

一、选择题：（本大题共10小题，每小题2分，共20分）1． 某内排序方法的稳定性是指( )。

A ．该排序算法不允许有相同的关键字记录 B ．该排序算法允许有相同的关键字记录 C ．平均时间为0（n log n ）的排序方法 D ．以上都不对2．下面程序段的时间复杂度为( )。

for(i=2;i<=n;++I) for(j=2;j<=i-1;++j) {++x;a[i ，j]=x;}A.O (1)B.O (log 2n )C.O (n )D.O (n 2)3．非空的循环单链表head 的尾结点p 满足( )。

A.p->next=head ；B. p->next=NULL ；C.p =NULL ；D. p->next->next =head ；4．设栈s 和队列Q 的初始状态为空， 元素b 1 ，b 2， ，b 3 ， b 4 ， b 5 和b 6 依次通过栈S ，一个元素出栈后即进队列Q ，若6个元素出队的序列是b 2 ，b 4 ，b 3 ，b 6 ，b 5 ，b 1 ， ，则栈S 的容量至少应该是( )。

题号 一二三四五六七八总分 复核人得分得分 评卷人………………………密……………………封…………………………装…………………订………………………线………………………系别 专业（班级） 姓名 学号A. 3B. 4C. 5D.其它5．表头和表尾均为空表的广义表是()。

A.()B.(())C.((()))D.(()，())6.下列二叉排序树中，满足平衡二叉树定义的是()。

A ． B.C. D.7．二维数组A的成员是4个字符（每个字符占一个存储单元）组成的串，行下标i的范围从1到8，列下标j的范围从1到10，若A按行优先方式存储，起始地址为SA，那么元素A[8][5]的起始地址为()。

“数据结构”期末考试试题一、单选题(每小题2分，共12分)1．在一个单链表HL中，若要向表头插入一个由指针p指向的结点，则执行( )。

A． HL＝ps p一>next＝HLB． p一>next＝HL；HL＝p3C． p一>next＝Hl；p＝HL；D． p一>next＝HL一>next;HL一>next＝p；2．n个顶点的强连通图中至少含有( )。

A.n—l条有向边B.n条有向边C.n(n—1)／2条有向边D.n(n一1)条有向边3.从一棵二叉搜索树中查找一个元素时，其时间复杂度大致为( )。

A.O(1)B.O(n)C.O(1Ogzn)D.O(n2)4．由权值分别为3，8，6，2，5的叶子结点生成一棵哈夫曼树，它的带权路径长度为( )。

A．24 B．48C． 72 D． 535．当一个作为实际传递的对象占用的存储空间较大并可能需要修改时，应最好把它说明为( )参数，以节省参数值的传输时间和存储参数的空间。

A.整形B.引用型C.指针型D.常值引用型·6．向一个长度为n的顺序表中插人一个新元素的平均时间复杂度为( )。

A．O(n) B．O(1)C．O(n2) D．O(10g2n)二、填空题(每空1分，共28分)1．数据的存储结构被分为——、——、——和——四种。

2．在广义表的存储结构中，单元素结点与表元素结点有一个域对应不同，各自分别为——域和——域。

3．——中缀表达式 3十x*(2.4／5—6)所对应的后缀表达式为————。

4．在一棵高度为h的3叉树中，最多含有——结点。

5．假定一棵二叉树的结点数为18，则它的最小深度为——，最大深度为——·6．在一棵二叉搜索树中，每个分支结点的左子树上所有结点的值一定——该结点的值，右子树上所有结点的值一定——该结点的值。

7．当向一个小根堆插入一个具有最小值的元素时，该元素需要逐层——调整，直到被调整到——位置为止。

《数据结构》期末考试试题及答案一、选择题（每题2分，共20分）1. 下列哪一个不是线性结构的基本特征？A. 有且只有一个根结点B. 每个结点最多有一个前驱和一个后继C. 有且只有一个叶子结点D. 有序对中第一个元素是根结点答案：C2. 在单链表中，存储元素的数据域称为元素的哪个部分？A. 指针域B. 数据域C. 结点域D. 头结点答案：B3. 在顺序存储结构中，数据元素之间的逻辑关系由哪个因素决定？A. 数据元素的存储顺序B. 数据元素的存储位置C. 数据元素的类型D. 数据元素的大小答案：A4. 下列哪种排序算法的时间复杂度不是O(nlogn)？A. 快速排序B. 归并排序C. 堆排序D. 冒泡排序答案：D5. 在二叉树中，具有度为2的结点的个数是n0，度为0的结点个数是n2，则有（）。

A. n0 = n2 - 1B. n0 = n2 + 1C. n0 = n2D. n0 = n2 + 2答案：B6. 在线索二叉树中，哪个结点被称为线索结点？A. 有左子树的结点B. 有右子树的结点C. 既没有左子树也没有右子树的结点D. 具有左右子树的结点答案：C7. 在双向链表中，查找结点的时间复杂度是（）。

A. O(1)B. O(n)C. O(nlogn)D. O(n^2)答案：B8. 在栈的操作中，下列哪个操作是非法的？A. 先进先出B. 后进先出C. 可以插入任意元素D. 可以删除任意元素答案：D9. 在顺序表中进行插入操作时，平均移动次数为（）。

A. 0B. n/2C. nD. n-1答案：C10. 在下列排序算法中，哪个算法是不稳定的？A. 冒泡排序B. 快速排序C. 插入排序D. 归并排序答案：B二、填空题（每题2分，共20分）1. 线性表的顺序存储结构称为顺序表，其基本特点是（）。

答案：元素顺序存储2. 在单链表中，每个结点包括两个域：数据域和（）。

答案：指针域3. 在二叉树中，度为0的结点称为（），度为2的结点称为（）。

《数据结构》试卷（B）学号：姓名：日期：一.选择题（每小题2分，共30分，请写在答卷纸上）：1.下面程序的时间复杂为（）。

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)2.设某数据结构的二元组形式表示为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是（）。

A.线性结构B.树型结构C.物理结构D.图状结构3.设指针变量p指向单链表中结点A，若删除单链表中结点A，则需要修改指针的操作序列为（）。

A.q=p->next；p->data=q->data；p->next=q->next；free(q)；B.q=p->next；q->data=p->data；p->next=q->next；free(q)；C.q=p->next；p->next=q->next；free(q)；D.q=p->next；p->data=q->data；free(q)；4.栈和队列的共同特点是( )。

A.只允许在端点处插入和删除元素B.都是先进后出C.都是先进先出D.没有共同点5.设某棵二叉树的中序遍历序列为ABCD，先序遍历序列为CABD，则后序遍历该二叉树得到序列为（）。

A.BADCB.BCDAC.CDABD.CBDA6.设有一个二维数组A[m][n]，假设A[0][0]存放位置在644(10)，A[2][2]存放位置在676(10)，每个元素占一个空间，问A[3][3](10)存放在什么位置？脚注(10)表示用10进制表示。

大学数据结构期末考试试题(有答案)大学数据结构期末考试试题(有答案)题一：单项选择题（共10题，每题2分，共20分）1. 数据结构是一种（）。

A. 算法B. 数据的存储结构C. 编程语言D. 操作系统答案：B2. 下列哪个不属于线性结构？A. 数组B. 栈C. 队列D. 树答案：D3. 栈是（）的一种典型应用。

A. 先进先出B. 先进后出C. 后进先出D. 后进后出答案：C4. 链表与数组的主要区别是（）。

A. 链表是动态分配的，数组是静态分配的B. 链表只能存储整数，数组可以存储任意类型的数据C. 链表的访问速度比数组快D. 链表的插入和删除操作比数组快答案：A5. 在二分查找算法中，查找元素的平均时间复杂度是（）。

A. O(n)B. O(logn)C. O(n^2)D. O(1)答案：B6. 以下哪种排序算法不是稳定的？A. 冒泡排序B. 快速排序C. 插入排序D. 归并排序答案：B7. 平衡二叉树的插入和删除操作的时间复杂度都是（）。

A. O(n)B. O(logn)C. O(n^2)D. O(1)答案：B8. 哈希表是通过（）实现的。

A. 数组B. 链表C. 树D. 图答案：A9. 拓扑排序是一种用来解决（）问题的算法。

A. 最短路径B. 最小生成树C. 最大流D. 有向无环图的排序答案：D10. 图的深度优先遍历算法使用（）来实现。

A. 栈B. 队列C. 数组D. 链表答案：A题二：填空题（共5题，每题4分，共20分）1. 顺序表中元素的逻辑顺序与物理位置相同，插入和删除操作会引起元素的（）。

答案：移动位置2. 在树的孩子兄弟表示法中，每个结点有两个指针，一个指向它的（），一个指向它的（）。

答案：第一个孩子，下一个兄弟3. 哈希表的存储时间和查找时间都为（）。

答案：O(1)4. 无向连通图的最小生成树边数为（）。

答案：n-1（n为结点个数）5. 平衡二叉树的定义是任意结点的左子树和右子树的高度差不超过（）。

武夷学院期末考试试卷（ 09级计算机科学与技术专业2010 ～2011 学年度第 1 学期） 课程名称 数据结构 A 卷 考试形式 闭卷 考核类型 考试 本试卷共 五 大题，卷面满分100分，答题时间120分钟。

一、选择题：（本大题共10小题，每小题2分，共20分）1． 某内排序方法的稳定性是指( )。

A ．该排序算法不允许有相同的关键字记录 B ．该排序算法允许有相同的关键字记录 C ．平均时间为0（n log n ）的排序方法 D ．以上都不对2．下面程序段的时间复杂度为( )。

for(i=2;i<=n;++I) for(j=2;j<=i-1;++j) {++x;a[i ，j]=x;}A.O (1)B.O (log 2n )C.O (n )D.O (n 2)3．非空的循环单链表head 的尾结点p 满足( )。

A.p->next=head ；B. p->next=NULL ；C.p =NULL ；D. p->next->next =head ；4．设栈s 和队列Q 的初始状态为空， 元素b 1 ，b 2， ，b 3 ， b 4 ， b 5 和b 6 依次通过栈S ，一个元素出栈后即进队列Q ，若6个元素出队的序列是b 2 ，b 4 ，b 3 ，b 6 ，b 5 ，b 1 ，，则栈S的容量至少应该是()。

A. 3B. 4C. 5D.其它5．表头和表尾均为空表的广义表是()。

A.()B.(())C.((()))D.(()，())6.下列二叉排序树中，满足平衡二叉树定义的是()。

A ． B. C. D.7．二维数组A的成员是4个字符（每个字符占一个存储单元）组成的串，行下标i的范围从1到8，列下标j的范围从1到10，若A按行优先方式存储，起始地址为SA，那么元素A[8][5]的起始地址为()。

A．SA+292 B．SA+296 C．SA+300 D．SA+3048．当在一个有序的顺序存储表上查找一个数据时，即可用折半查找，也可用顺序查找，但前者比后者的查找速度()。