计本06级《数据结构》B卷参考答案及评分标准finish

适用专业：一、单项选择题（每题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]。

数据结构期末考试试题和标准答案及评分标准《数据结构》试题（A卷）（考试时间： 90分钟）一、单项选择题（本大题共15小题，每小题2分，共30分）（每题只有一个选项是正确的,将答案填写在括号内，错选、多选不得分）1.（）是组成数据的基本单位，是一个数据整体中相对独立的单元。

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

A.效率B.复杂度C.数据元素之间的关系??? ?D.数据的存储方法3.若某线性表最常用的操作是存取任一指定序号的元素和在最后进行插入或删除运算，则采用以下（）方式最节省时间。

A.链式存储B. 索引存储C.顺序存储D.散列存储4.下述哪一条是顺序存储结构的优点？（）A.存储密度大?B.插入运算方便?C.删除运算方便?D.可方便地用于各种逻辑结构的存储表示5.在一个单链表中，若删除p所指结点的后续结点，则执行（）。

>next=p->next->next >next=p->next=p->next;p->next=p->next->next =p->next->next6.带头结点的单链表head为空的判定条件是（）。

==NULL >next==NULL >next==head !==NULL7.非空的循环单链表head的尾结点(由p所指向)满足（）。

>head==NULL ==NULL >next==head ==head8.下面关于线性表的叙述中，错误的是哪一个？（）A.线性表采用顺序存储，必须占用一片连续的存储单元。

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

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

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

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

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

一、单项选择题（2分×10=20分）1．若某线性表中最常用的操作是提取第i个元素及找第i个元素的前驱元素，则采用（ D ）存储方式最省时间。

A.单链表B.双链表C.单向循环链表D.顺序表2．将含有100个结点的完全二叉树从根开始自上向下，每层从左到右依次编号，且设根结点的编号为1，则编号69的结点的双亲的编号为（ A ）。

A. 34B. 35C. 33D. 无法确定3. 单循环链表的主要优点是（D ）。

A. 不再需要头指针了B. 已知某结点的位置后，很容易找到其前驱C. 在进行插入、删除运算时，能更好地保证链表不断开D. 从表中任一结点出发都能扫描到整个链表4. 在长为n的顺序表中，向第i个元素(1≤i≤n+1)前插入一个元素需要向后移动（ B ）个元素。

A. n-iB. n-i+1C. n-i-1D. i5. 一个栈的入栈顺序是1、2、3、4、5，则此栈不可能的输出顺序为（ C ）。

A. 5、4、3、2、1B. 4、5、3、2、1C. 4、3、5、1、2D. 1、2、3、4、56. 串是一种特殊的线性表，其特殊性表现在（ B ）。

A. 可以顺序存储B.数据元素是一个字符C可以链式存储 D.数据元素是多个字符7. 一棵5层满二叉树中，结点总数为（C ）个。

A. 33B.32C.31D.308. 下列4棵二叉树，（ B ）是平衡树。

A. B. C. D.9. n个顶点的无向图中最多有（A ）条边。

A. n(n-1)/2B. n(n-1)C. n(n+1)D. n(n+1)/210. 6个顶点的无向图中，至少有（A ）条边才能保证是一个连通图。

A. 5B. 6C. 7D. 8二、判断题（1分×10=10分）（F ）1. 线性结构的基本特征是：每个结点有且仅有一个直接前驱和一个直接后继。

（F ） 2. 二叉树是树的特殊情形。

（T ）3. 存在这样的二叉树，其先序遍历与中序遍历得到的访问序列相同。

一、（本题15分）试设计一个结点数据类型为整型的带表头结点的有序单链表，然后设计一个算法，该算法将这个有序单链表划分成两个单链表，使得第一个单链表中包含原单链表中所有数值为奇数的结点，第二个单链表中包含原单链表中所有数值为偶数的结点，且两个单链表中结点的相对排列顺序与原单链表中相同。

注意：要求使用原单链表的空间，表头结点可以另辟空间。

[解答]void split(LinkList &HL, LinkList &L1, LinkList &L2) {q1=L1= (LinkList) malloc(sizeof(LNode));q2=L2= (LinkList) malloc(sizeof(LNode));p=HL->next;while (p!=NULL) {if (p->date % 2 != 0) {q1->next= p; q1=p;}elseq2->next= p; q2=p;}p=p->next;}q1->next=q2->next=NULL;free(HL);}二、（本题20分）试设计一个递归算法，判断二叉树T是否是满二叉树，假设T是以二叉链表存储。

typedef struct BiTNode{TElemType data;Struct BiTNode *lchild, *rchild;} BiTNode, *BiTree;解答：满二叉树中任一个结点为根的子树都是满二叉树。

算法：（1）如果二叉树T是空树，则是满二叉树；（2）如果二叉树T非空，左右子树都是满二叉树，而且深度一样，则T是满二叉树；（3）如果二叉树T非空，左子树或右子树不是满二叉树，则不是满二叉树；（4）如果二叉树T非空，左右子树都是满二叉树，但深度不一样，则T不是满二叉树。

//该函数判断二叉树T 是否是满二叉树//如果是满二叉树，返回TRUE ，Depth 返回该树的深度； //否则返回FALSE ，Depth 无定义； Boolean Check( BiTree T, int &Depth) { int ldepth, rdepth;if( T==NULL) { Depth=0; return TRUE; }if( Check(T->lchild, ldepth)==FALSE ) return FALSE; if( Check(T->rchild,rdepth)==FALSE) return FALSE; if( ldepth!=rdepth ) return FALSE; Depth=ldepth+1; return TRUE; }三、（本题15分）给定下面的带权无向图G ：1） 从顶点0出发，请写出深度优先遍历序列和广度优先遍历序列，当有多种选择时，编号小的结点优先。

数据结构试卷B卷(含答案)-CAL-FENGHAI.-(YICAI)-Company One1《数据结构》试卷B一、填空题（每空1分，共15分）1. 向量、栈和队列都是结构，可以在向量的位置插入和删除元素；对于栈只能在插入和删除元素；对于队列只能在插入和删除元素。

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

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

3. 数据结构是一门研究非数值计算的程序设计问题中计算机的以及它们之间的和运算等的学科。

4. 在顺序表中插入或删除一个元素，需要平均移动元素，具体移动的元素个数与有关。

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

6. 假设在有序线性表a[20]上进行折半查找，则比较一次查找成功的结点数为1；比较两次查找成功的结点数为；比较四次查找成功的结点数为；平均查找长度为。

二、判断正误（判断下列概念的正确性，并作出简要的说明。

）（每小题1分，共10分）（）1. 线性表的每个结点只能是一个简单类型，而链表的每个结点可以是一个复杂类型。

（）2. 在表结构中最常用的是线性表，栈和队列不太常用。

（）3. 栈是一种对所有插入、删除操作限于在表的一端进行的线性表，是一种后进先出型结构。

（）4. 对于不同的使用者，一个表结构既可以是栈，也可以是队列，也可以是线性表。

（）5.线性表的逻辑顺序与存储顺序总是一致的（）6. 栈和队列是一种非线性数据结构。

（）7. 栈和队列的存储方式既可是顺序方式，也可是链接方式。

（）8. 两个栈共享一片连续内存空间时，为提高内存利用率，减少溢出机会，应把两个栈的栈底分别设在这片内存空间的两端。

（）9. 队是一种插入与删除操作分别在表的两端进行的线性表，是一种先进后出型结构。

（）10. 一个栈的输入序列是12345，则栈的输出序列不可能是12345。

三、单项选择题（每小题1分，共20分）（）1．数据在计算机存储器内表示时，物理地址与逻辑地址相同并且是连续的，称之为：（A）存储结构（B）逻辑结构（C）顺序存储结构（D）链式存储结构（）2. 若已知一个栈的入栈序列是1，2，3，…，n，其输出序列为p1，p2，p3，…，pn，若p1=n，则pi为Ａ．i Ｂ．n=i Ｃ．n-i+1 Ｄ．不确定（）3. 判定一个栈ST（最多元素为m0）为空的条件是Ａ．ST->top<>0 Ｂ．ST->top=0 Ｃ．ST->top<>m0 Ｄ．ST->top=m0（）4设矩阵A是一个对称矩阵，为了节省存储，将其下三角部分（如下图所示）按行序存放在一维数组B[ 1, n(n-1)/2 ]中，对下三角部分中任一元素a i,j(i≤j), 在一维数组B中下标k的值是：Ａ．i(i-1)/2+j-1 Ｂ．i(i-1)/2+j Ｃ．i(i+1)/2+j-1 Ｄ．i(i+1)/2+j（ ）5．具有n(n>0)个结点的完全二叉树的深度为 。

上海电机学院继续教育学院2017 学年上半年期末考试试卷B(数据结构) 课程试卷班级：成1675 学号：姓名：(本卷考试时间90分钟)题号一二三四五六总得分题分得分数据结构B卷参考答案一、选择题1.B2.B3.A4.A5.A6.B7.D8.C9.B 10.D二、填空题1. 顺序存储结构、链式存储结构2. 9，5013. 54. 出度，入度5. 06. e=d7. 中序8. 79. O(1)10. i/2，2i+111. (5，16，71，23，72，94，73)12. (1，4，3，2)13. j+1，hashtable[j].key==k14. return(t)，t=t->rchild三．程序填空1．答：①i=1②a[i]>b2．答：③(n%10)*(n%10_)④n/10⑤n四．试编以下完整程序：1．有一函数x (x<1)y= 2x+10 (1≤x<10)3x+9 ( x≥10)写一程序，输入x,输出y值。

1.#include<iostream.h>void main(){ float x,y;cin>>x;if(x<1) y=x;else if(x<10) y=2*x+10;else y=3*x+9;cout<<"x= "<<x<<" y= "<<y<<endl;}2．输入一行字符到数组C[80]中，分别统计其中大写和小写英文字母的个数。

以上功能可反复直至选择退出。

#include <iostream.h>#include <stdio.h>#include <string.h>void main(){int k,m=0,b,p=0;char c[80],n='y';do{cout<<"请输入字符"<<endl;gets(c);k=strlen(c); //计算字符数cout<<"一共有"<<k<<"个字符"<<endl;for(b=0;b<k;b++)if(c[b]>='A'&&c[b]<='Z')m++; //计算大写英文个数else if(c[b]>='a'&&c[b]<='z')p++; //计算小写英文个数cout<<"继续吗？(y/n)";cin>>n;}while(n=='y');cout<<"有"<<p<<"小写英文字符"<<endl;cout<<"有"<<m<<"大写英文字符"<<endl; }。

南京 林 业 大 学 试 卷课程 数据结构(B 卷) 2006~2007学年第一学期注意：请将正确答案写在答题纸上，答在试卷上不给分。

一．是非题：（每小题2分，共20分）1．数据的物理结构是指数据在计算机内实际的存储形式。

（ ） 2．顺序存储的线性表可以随机存取。

（ ） 3．链表中的每个结点中都恰好包含一个指针。

（ ）4．线性表可以看成是广义表的特例，如果广义表中的每个元素都是原子，则广义表便成为线性表。

（ ）5．任意的一棵树转换成二叉树，其根结点的右子树总不为空。

（ ） 6．简单模式匹配算法的最大特点是指示主串的指针不需回溯。

（ ）7．用邻接矩阵存储一个图时，在不考虑压缩存储的情况下，所占用的存储空间大小与图中的边数有关。

（ ）8．任何有向图的拓扑排序结果是唯一的。

（ ）9．哈希表存储的基本思想是由记录关键字值决定记录的存储地址。

（ ） 10．堆排序所需的时间与待排序的记录个数无关。

（ ）二．选择题（本大题共10小题，每小题2分，共20分）1． 在数据结构中，与所使用的计算机无关的是数据的______结构。

A. 存储 B. 物理 C. 逻辑 D. 物理和逻辑2．链表不具有的特点是______。

A.可随机访问任一元素B.插入删除不需要移动元素C.不必事先估计存储空间D.所需空间与线性表长度成正比3．一个顺序栈一旦被说明，所占用的空间大小________。

A．不能固定B．已固定C．可以改变D．随机变化4．下列关于串的叙述中，正确的是________。

A．一个串的字符个数即该串的长度B．一个串的长度至少是1C．空串是由一个空格字符组成的串D．两个串的长度相等，则这两个串相等5．下列广义表是线性表的是________。

A．L=(x,y,(x,y),x) B．L=(a,(a,b)) C．L=(x,y,z) D．L=(x,L,y)6．一棵二叉排序树，用______ 方法进行遍历，可得到各结点关键字值的递增序列。

《数据结构B卷》期末考试试卷附答案一、名词解释(每题2分，共10分)1. 数据类型2. 线性表3. 队列4. 串5. 图二、判断正误(正确打√，错误划×，每题1分，共10分)1.算法必须有输入参数。

( )2.链表能够动态分配结点空间。

( )3.栈是一种先进先出的线性表。

( )4.二维数组能够实现随机存取。

( )5.在二叉树的第i层上至多有2i-1个结点(i≥1)。

( )6.在有向图中，<v1,v2>与<v2,v1>是两条不同的边。

( )7.邻接表只能用于有向图的存储。

（）8.有向图不能进行广度优先遍历( )9.平均查找长度ASL可作为衡量一个查找算法效率高低的标准。

( )10.所有的内部排序算法都是稳定的。

( )三、填空(每空2分，共10分)1.线性表、栈和队列都是( )结构。

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

3.队列的出队操作总是在( )进行。

4.按存储结构不同，串可分为( )。

5.深度为k 的完全二叉树至少有( )个结点。

四、选择题(单选或多选)(每题2分，共30分)1.算法原则上都是能够由机器或人完成的。

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

这是算法的( )。

A. 正确性B. 有穷性C. 确定性D. 可行性2.设一棵二叉树中，度为2的结点数为9，则该二叉树的叶结点的数目为( )。

A．10 B. 11 C. 12 D. 不确定3.某二叉树结点的先根序列为E、A、C、B、D、G、F，对中根遍历的序列为A、B、C、D、E、F、G。

该二叉树结点的后根遍历的序列为( )A. [B 、D 、C 、A 、F 、G 、E]B. [B 、D 、C 、F 、A 、G 、E]C. [E 、G 、F 、A 、C 、D 、B]D. [E 、G 、A 、C 、D 、F 、B]4.关于队列的说法正确的是（）A. 先进先出B. 属于非线性结构C. 只能采用顺序存储D.属于散列结构5.用单链表表示的链式队列的队尾是在链表的( )位置A. 表尾B. 表头C. 表中D. 任意6.树的非叶子结点是（）。