下载文档原格式
适用专业：一、单项选择题（每题2分，共40分）1．算法的时间复杂度是指( )A．执行算法程序所需要的时间B．算法程序的长度C．算法执行过程中所需要的基本运算次数D．算法程序中的指令条数2．在一个单链表HL中，若要删除由指针q所指向结点的后继结点，则执行（）。
A．p = q->next ; p->next = q->next; B．p = q->next ; q->next = p;C．q->next = q->next->next; q->next = q; D．p = q->next ; q->next = p->next; 3．下列叙述中正确的是( )A．线性表是线性结构 B. 栈与队列是非线性结构C．线性链表是非线性结构 D. 二叉树是线性结构4．若让元素1，2，3依次进栈，则出栈次序不可能出现（）种情况。
A．3，2，1 B．2，1，3 C．3，1，2 D．1，3，25．图的广度优先搜索类似于树的（）次序遍历。
A．先根B．中根C．后根D．层次6．具有n个顶点的有向无环图最多可包含（）条有向边。
A．n-1 B．n C．n(n-1)/2 D．n(n-1)7．已知单链表A长度为m，单链表B长度为n，若将B联接在A的末尾，其时间复杂度应为( ) 。
A．O(1) B．O(m) C．O(n) D．O(m+n)8．若要在单链表中的结点*p之后插入一个结点*s，则应执行的语句是( )。
A．s->next=p->next; p->next=s; B．p->next=s; s->next=p->next;C．p->next=s->next; s->next=p; D．s->next=p; p->next=s->next;9．假定一个链式队列的队头和队尾指针分别为front和rear，则判断队空的条件为( )。
专升本《数据结构》_试卷_答案专升本《数据结构》一、（共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的链式栈中入栈实现算法的时间复杂度为（）。
2006年下半年全国自考（数据结构）真题试卷(题后含答案及解析)题型有：1. 单项选择题 2. 填空题 3. 解答题 4. 算法阅读题 5. 算法设计题单项选择题1．数据结构是( )A．一种数据类型B．数据的存储结构C．一组性质相同的数据元素的集合D．相互之间存在一种或多种特定关系的数据元素的集合正确答案：D2．算法分析的目的是( )A．辨别数据结构的合理性B．评价算法的效率C．研究算法中输入与输出的关系D．鉴别算法的可读性正确答案：B3．在线性表的下列运算中，不改变数据元素之间结构关系的运算是( )A．插入B．删除C．排序D．定位正确答案：D4．若进栈序列为1,2,3,4,5,6，且进栈和出栈可以穿插进行，则可能出现的出栈序列为( )A．3,2,6,1,4,5B．3,4,2,1,6,5C．1,2,5,3,4,6D．5,6,4,2,3,1正确答案：B5．设串s1=“Data Structures、with Java”，s2=“it”，则子串定位函数index(s1，s2)的值为( )A．15B．16C．17D．18正确答案：C6．二维数组A[8][9]按行优先顺序存储，若数组元素A[2][3]的存储地址为1087，A[4][7]的存储地址为1153，则数组元素A[6][7]的存储地址为( ) A．1207B．1209C．1211D．1213正确答案：A7．在按层次遍历二叉树的算法中，需要借助的辅助数据结构是( ) A．队列B．栈C．线性表D．有序表正确答案：A8．在任意一棵二叉树的前序序列和后序序列中，各叶子之间的相对次序关系( )A．不一定相同B．都相同C．都不相同D．互为逆序正确答案：B9．若采用孩子兄弟链表作为树的存储结构，则树的后序遍历应采用二叉树的( )A．层次遍历算法B．前序遍历算法C．中序遍历算法D．后序遍历算法正确答案：C10．若用邻接矩阵表示一个有向图，则其中每一列包含的”1”的个数为( )A．图中每个顶点的入度B．图中每个顶点的出度C．图中弧的条数D．图中连通分量的数目正确答案：A11．图的邻接矩阵表示法适用于表示( )A．无向图B．有向图C．稠密图D．稀疏图正确答案：C12．在对n个关键字进行直接选择排序的过程中，每一趟都要从无序区选出最小关键字元素，则在进行第i趟排序之前，无序区中关键字元素的个数为( )A．iB．i+1C．n-iD．n-i+1正确答案：D13．下列排序算法中，其时间复杂度和记录的初始排列无关的是( ) A．插入排序B．堆排序C．快速排序D．冒泡排序正确答案：B14．若有序表的关键字序列为(b,c,d,e,f,g,q,r,s,t)，则在二分查找关键字b的过程中，先后进行比较的关键字依次为( )A．f,c,bB．f,d,bC．g,c,bD．g,d,b正确答案：A15．若在文件中查询年龄在60岁以上的男性及年龄在55岁以上的女性的所有记录，则查询条件为( )A．(性别=“男”)OR(年龄＞60)OR(性别=“女”)OR(年龄＞55)B．(性别=“男”)OR(年龄＞60)AND(性别=“女”)OR(年龄＞55)C．(性别=“男”)AND(年龄＞60)OR(性别=“女”)AND(年龄＞55)D．(性别=“男”)AND(年龄＞60)AND(性别=“女”)AND(年龄＞55)正确答案：C填空题16．称算法的时间复杂度为O(f(n))，其含义是指算法的执行时间和______的数量级相同。
中南财经政法大学2005 –2006 学年第2 学期期末考试试卷答案课程名称：《数据结构》（B）卷课程代号： 09091051考试形式：闭卷、笔试使用对象：电子政务专业一、单选题：（共25题，每题1分，共25分）二、多选题：（共5题，每题2分，共10分）三、填空题：（共6题，每空1分，共10分）1.线性结构和非线性结构。
2.O（n）3. (m+1)%n4.n5.索引表6.插入排序、交换排序、选择排序、归并排序、基数据排序。
四、判断题：（共5题，每题2分，共10分）五、简答题：（共5题，每题5分，共25分）1.2.试比较顺序存储结构和链式存储结构的优劣性答：(1)由于链式存储结构可以用任意的存储空间来存储线性表中的各数据元素，且其存储空间可以是连续的，也可以不连续；此外，这种存储结构对元素进行插入和删除操作时都无需移动元素，而仅仅修改指针即可，所以很适用于容量变化的情况。
（2分）(2)由于顺序存储结构一旦确定了起始位置，数据结构中的任何一个元素都可以通过函数进行随机存取，即存取速度较高：并且，由于数据的总数基本稳定，在很少进行插入和删除的结构中应选用顺序存储结构。
（3分）3.4.试证明有n0个叶子结点的哈夫曼树共有2n0-1个结点。
证明：（1）在哈夫曼树中，只有度为0和度为2 的结点。
所以，n=n0+n2 （3分） （2）以由性质知，n0=n2+1， 所以，n=n0+n0-1=2n0-1。
（2分） 5. 给出下面二叉树的中序线索树。
6. 给出图的所有顶点间的最短路径（给出步骤，从第二步每步1分）。
结果：5.六、算法填空：（共2题，每空2 分，共14分）。
一、单项选择题（每小题2分，共30分）1.下列关于栈的叙述中，正确的是（）。
A．栈底元素一定是最后入栈的元素B．栈操作遵循先进后出的原则C．栈顶元素一定是最先入栈的元素D．以上三种说法都不对2.在数据结构中，与所使用的计算机硬件无关的是数据的（）结构。
A．逻辑B．存储C．逻辑和存储D．物理3.以下说法正确的是（）。
A．数据项是数据的基本单位B．数据元素是数据的最小单位C．数据结构是带结构的数据项的集合D．一些表面上很不相同的数据可以有相同的逻辑结构4.六个元素按照6，5，4，3，2，1的顺序入栈，下列哪一个是合法的出栈序列？（）A．546132 B．453126 C．346512 D．2341565.设树的度为4，其中度为1、2、3、4的结点个数分别是4、2、1、2，则树中叶子个数为（）A．8 B．9 C．10 D．116.分别用以下序列构造二叉排序树，与用其他三个序列构造的结果不同的是（）A.（100,80,90,60,120,110,130）B.（100, 120, 110,130,80, 60,90）C.（100,60,80,90,120,110,130）D.（100,80, 60,90, 120, 130,110）7.下列陈述中正确的是（）A．二叉树是度为2的有序树B．二叉树中结点只有一个孩子时无左右之分C．二叉树中必有度为2的结点D．二叉树中最多只有两棵子树，并且有左右之分8.在含n个顶点和e条边的无向图的邻接矩阵中，零元素的个数为（）A．e B．2e C．n2－e D．n2－2e9.栈和队列都是（）A．限制存取位置的线性结构B．顺序存储的线性结构C．链式存储的线性结构D．限制存取位置的非线性结构10.在具有n个叶子结点的严格二叉树（即结点的度要么是0要么是2）中，结点总数为（）A．2n+1 B．2n C．2n-1 D．2n-211.在循环双链表的p所指的结点之前插入s所指结点的操作是（）。
二1A三判断题（10分）（评分标准:2 V 3X 4 V 5X 6X 7 V选择题（202A 3A 4C 5B填空题（20分）（评分标准:6C 7C 8C（评分标准:每小题1分）8 V 9X 10X每小题2分）9C 10B每空1分）《数据结构与算法》试卷B答案及评分标准1.线性，非线性2.』3・链接（或链式）4.表屮一半,表长度和该元素衣表屮的位置5. nd 6.移动栈顶指针，存入元素7. 5 &遍历左了树,遍历右了树,访问根结点9. 0, n（n・l）/2 l（k 11.关键字相同的记录12. 3_ 13.插入,选择四、简答题（20分）（评分标准：每小题4分）1 •答：①顺序存储时，相邻数据元素的存放地址也相邻（逻辑与物理统一）；要求内存屮可用存储单元的地址必须是连续的。
优点：存储密度大（ = 1?）,存储空间利用率高。
缺点：插入或删除元素时不方便。
②链式存储时，相邻数据元素可随意存放，但所占存储空间分两部分，一部分存放结点值，另一部分存放表示结点间关系的指针优点：插入或删除元素时很方便，使用灵活。
缺点：存储密度小（V1）,存储空间利用率低。
顺序表适宜于做查找这样的静态操作；链表宜于做插入、删除这样的动态操作。
若线性表的长度变化不大，且其主要操作是杳找，则采用顺序表；若线性表的长度变化较大，且-其主要操作是插入、删除操作, 则采用链表。
2•答：首元结点是指链表中存储线性表屮第一个数据元素迈的结点。
为了操作方便，通常在链表的首元结点Z 前附设一个结点，称为头结点，该结点的数据域屮不存储线性表的数据元素，其作用是为了对链表进行操作时，可以对空表、非空表的情况以及对首元结点进行统一处理。
头指针是指向链表屮第一个结点（或为头结点或为首元结点）的指针。
若链表屮附设头结点，则不管线性表是否为空表，头指针均不为空。
否则表示空表的链表的头指针为空。
这三个概念对单链表、双向链表和循环链表均适用。
是否设置头结点, 是不同的存储结构表示同一-逻辑结构的问题。
华东交通大学2012—2013学年第一学期考试卷试卷编号： （B ）卷数据结构 课程 课程类别：必考生注意事项：1、本试卷共5页，总分100分，考试时间120分钟。
2、考试结束后，考生不得将试卷、答题纸和草稿纸带出考场。
一、选择题(每题2分，共20分)1、栈和队列的共同特点是( A )。
A.只允许在端点处插入和删除元素B.都是先进后出C.都是先进先出D.没有共同点2、用链接方式存储的队列，在进行插入运算时( D ).A. 仅修改头指针B. 头、尾指针都要修改C. 仅修改尾指针D.头、尾指针可能都要修改 3、以下数据结构中哪一个是非线性结构？( D )A. 队列B. 栈C. 线性表D. 二叉树4、 设指针变量p 指向单链表中结点A ，若删除单链表中结点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)；5、 若有18个元素的有序表存放在一维数组A[19]中，第一个元素放A[1]中，现进行二分查找，则查找A ［3］的比较序列的下标依次为( D )A. 1，2，3B. 9，5，2，3C. 9，5，3D. 9，4，2，3承诺：我将严格遵守考场纪律，知道考试违纪、作弊的严重性，还知道请他人代考或代他人考者将被开除学籍和因作弊受到记过及以上处分将不授予学士学位，愿承担由此引起的一切后果。
专业 班级 学号 学生签名：6、设某棵二叉树的中序遍历序列为ABCD，前序遍历序列为CABD，则后序遍历该二叉树得到序列为（ A ）。
《数据结构》试卷（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进制表示。
《数据结构》试卷（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进制表示。
一、单项选择题（本大题共15小题，每小题2分，共30分） 1-5 BAACB 6-10 ADACA 11-15 ACCBB二、填空题(本大题共10个空，每空1分，共10分)16. e=d 17. O(n 2) 18. 17 71 19. 4 ， 10 20. N-1 21.线性结构，树型结构，图型结构三、判断题（本大题共10小题，每个1分，共10分）22.× 23.√ 24.× 25. √ 26.√ 27. × 28.× 29.× 30.√ 31.×四、应用题(本大题共4小题，每小题10分，共40分)。
32.可能的序列：a b c a c b b a c b c a c b a .............（5分） 对应的操作序列依次为:(1)push(a), pop(a), push(b), pop(b), push(c), pop(c) (2)push(a), pop(a), push(b), push(c), pop(c), pop(b) (3)push(a), push(b), pop(b) , pop(a), push(c), pop(c) (4)push(a), push(b), pop(b), push(c), pop(c) , pop(a) (5)push(a), push(b), push(c), pop(c), pop(b) , pop(a).............（每个序列１分）33. (4) .............（6分）0 2 3 1 434.....................（画出此树可得7分）。
(2) a：0101， b：10， c：01000， d：11， e：011， f：000， g：01001，h：001 ................... (3分)35. 根据题目给定的散列函数H(K)=K%13,其值域为0～12，可设计用于指向单链表的散列表表头数组HT[0…12]。
计本通信06级《数据结构》B卷参考答案及评分标准
一、单项选择题(每题 2分，共 20 分)
1~5：A BA D D 6~10：B D B B D
二、判断题(每题 1 分，共 8 分，对的打“√”，错的打“X”)
X X√X X X X X
三、填空题(每空1分，共20分)
1．(集合，线性结构，树形结构)
2．_数据、_操作.
3．前移、p->next、s 、链域数目不同
4．138
5．_线性
6．(a,b)、(c,d) 、_ n-1.
7．_ 180 、6644
8．时间、空间
9．(栈顶、栈底)
四、简答或构造题(每小题4分，共24分)
1．解答：(10 20 25 5 31 16 44 61 3 100 )
(10 20 5 25 16 31 44 3 61 100)
(10 5 20 16 25 31 3 44 61 100))
(5 10 16 20 25 3 31 44 61 100 )
2．解答： A
B F
C G
D E H
3.解：可以通过穷举所有可能性来求解：
① 1入1出， 2入2出，3入3出，即123；
② 1入1出， 2、3入，3、2出，即132；
③ 1、2入，2出， 3入3出，即231；
④ 1、2入，2、1出，3入3出，即213；
⑤ 1、2、3入，3、2、1出，即321；
合计有5种可能性。
4. DFS 结果：v1 → v2 → v4 → v8 →v5 →v3 →v6 → v7
BFS 结果：v1 → v2 → v3 →v4 → v5 → v6 →v7 → v8
5.
6.所构造的哈夫曼树:
每个字符对应的编码: a(11)
b(1010) c(100) d(01)
e(1011) f(00)
图2分，编码2分，不满足左孩子结点的权值小于右孩子结点的权值的扣1分
五、综合应用题(共8分)
解：用线性探测再散列处理冲突，即Hi=(H(key)+di) MOD m
与地址（0..17）对应的元素值为
(null,14,1,68,27,55,19,20,84,79,23,11,10,null,null,null)
ASL=(1*6+2+3*3+4+9)/12=2.5
H(84)=6 冲突，
H1=(6+1)MOD16=7 冲突，
H2=(6+2)MOD16=8
要求有中间处理冲突的过程，否则扣2分
六、算法设计题(共10+10分)
要求算法正确
1. void Maopao(int a[], int n)
{
for(int i=1; i<=n; i++)
{
for(int j=1; j<=n-i; j++)
{
if(a[j]>a[j+1])
{
int temp = a[j]; a[j] = a[j+1]; a[j+1] = temp; }
}
}
}
2．解：
int InOrderTraverse(BiTree T)
{
InitStack(S);
p = T;
while( p||!Stackempty(S) )
{
if(p)
{
push(S,p);
p = p->lc;
}
else
{
pop(S,p);
printf(" %d", p->data);
p = p->rc;
}
}
return 1;
}
.3.
void unin(linklist *heada,linklist *headb) { linklist *p,*q,*r,*u;
p=heada->next;
r=heada;
while (p!=NULL) &&(q!=NULL)
{ if (p->data>q->data)
{ u=q-next;
r->next=q;
q->next=p;
q=u;。
