数据结构考试试题带答案文档格式.docx

1、（说明：请将答案填入下表中）12345678910答案ABDC11121314151.若某线性表最常用的操作是存取任一指定序号的元素和在最后进行插入和删除运算，则利用（A）存储方式最节省时间。A顺序表 B双链表 C带头结点的双循环链表 D单循环链表2.设a1、a2、a3为3个结点，则如下的链式存储结构称为：表元编号结点表元间关系a1a2a3A循环链表 B单链表 C双向循环链表 D双向链表3.有六个元素6，5，4，3，2，1 的顺序进栈，问下列哪一个不是合法的出栈序列？（B ）A. 5 4 3 6 1 2 B. 3 4 6 5 2 1 C. 4 5 3 1 2 6 D. 2 3 4 1 5 64

2、.若栈采用顺序存储方式存储，现两栈共享空间V1.m，topi代表第i 个栈（ i =1,2）栈顶，栈1 的底在v1，栈2 的底在Vm，则栈满的条件是（B ）。A. top2-top1|=0 B. top1+1=top2 C. top1+top2=m D. top1=top25.数组用来表示一个循环队列，front为当前队列头元素的前一位置，rear为队尾元素的位置，假定队列中元素的个数小于，计算队列中元素的公式为（D）A. rearfront B.（nfrontrear）% nC. nrearfront D.（nrearfront）% n6.设栈S 和队列Q 的初始状态为空，元素e1，e2，e

3、3，e4,e5 和e6 依次通过栈S，一个元素出栈后即进队列Q，若6 个元素出队的序列是e2，e4,e6,e5，e3,e1 则栈S 的容量至少应该是（ B）。A 6 B. 4 C. 3 D. 27.在数据结构中，从逻辑上可以把数据结构分成（ C）。8. A动态结构和静态结构 B紧凑结构和非紧凑结构9. C线性结构和非线性结构 D内部结构和外部结构10.判定一个顺序栈ST（最多元素为N）为空的条件是 （B ）。ASTtop ！= ST.base BSTtop=ST.base CSTtop！=N DSTtop=N11.一个队列的入列序列是1，2，3，4，则队列的输出序列是 B 。 A4,3,2,1

4、 B1,2,3,4 C1,4,3,2 D3,2,4,112.判定一个循环队列QU（最多元素为N）为空的条件是 C 。 AQU.front= （QU.rear+1）%N BQU.front！= （QU.rear+1）%N CQU.front= QU.rear DQU.front！= QU.rear 13.判定一个循环队列QU（最多元素为m0）为满队列的条件是 A 。 AQU.front= （QU.rear+1）%N BQU.front！= QU.rear+114.不带头结点的单链表head为空的判定条件是 A Ahead=NULL Bhead - next=NULL Chead- next=he

5、ad Dhead!=NULL15.15.在双向链表指针p 的结点前插入一个指针q 的结点操作是（C ）。A. p-Llink=q;q-Rlink=p;p-Llink-Rlink=q;Llink=q；B. p-Llink=p-Llink;C. q-D. q-16.从一个具有n个结点的单链表中查找其值等于x结点时，在查找成功的情况下，需平均比较_D_个结点。An Bn/2 C（n1）/2 D（n+1）/217.设串s1=ABCDEFG,s2=PQRST,函数con（x,y）返回x和y串的连接串，subs（s,i,j）返回串s的从序号i的字符开始的j个字符组成的字串， len（s）返回串s的长度，则

6、con（subs（s1,2,len（s2）, subs（s1,len（s2）,2）的结果串是 D A）BCDEF B）BCDEFG C）BCPQRST D）BCDEFEF三综合题（每题6分，共30分）1.线性表具有两种存储方式，即顺序方式和链接方式。现有一个具有五个元素的线性表L=23，17，47，05，31，若它以单链表方式存储在下列100119号地址空间中，每个结点由数据（占2个字节）和指针（占2个字节,由大写字母表示）组成，如下所示：其中指针p，q，r，s，t的值分别为多少？该线性表的首结点起始地址为多少？末结点的起始地址为多少？（共6分）2.答：p= 108 q = 116 r = 1

7、12 s= 0 或NULL t= 100 首址= 104 末址= 112 。3.如果想将输入的一个字符序列逆序输出，如输入“abcdef ”，输出“fedcba”，请分析用线性表、堆栈和队列等方式正确输出的可能性？ （共6分）线性表是随机存储，可以实现，靠循环变量（j-）从表尾开始打印输出；堆栈是后进先出，也可以实现，靠正序入栈、逆序出栈即可；队列是先进先出，不易实现。4.写出删除顺序表中第i个元素的算法：Status ListDelete_sq（SqList &L, int i, ElemType &e）Status del_sqllist（SqList &L,int i, ElemType

8、 & if （i L.length） return ERROR; e= L.elemi; for （j=i+1;j data = e; p-next=S.top ;/ 链接到原来的栈顶S.top = p; / 移动栈顶指针+S.length;/ 栈的长度增1 / Push6.写出链队列的出队列算法（共6分）Status DeQueue（LinkQueue &Q, QelemType & Status DeQueue （LinkQueue &Q, QElemType &e） / 若队列不空，则删除Q的队头元素， /用 e 返回其值，并返回OK；否则返回ERROR if （Q.front = Q.

9、rear） return ERROR; p = Q.front-next; e = p-data; Q.front-next = p- if （Q.rear = p） Q.rear = Q.front; free （p）;科技大学成都学院20082009学年第一学期中期试题数据结构答案一填空题（每题2分，共40分）；参考答案空间复杂度O（n2）下一结点的地址线型，任意，栈顶，队尾，队头n-1n-i+1前驱head-next= =NULLhs= =NULLhq.front-next=hq.rearnext=head串长相等且对应字符相等长度为0的串，0由空格字符组成的串，空格的个数三综合题（共3

10、0分）7.p= 108 q = 116 r = 112 s= 0 或NULL 8.线性表是随机存储，可以实现，靠循环变量（j-）从表尾开始打印输出；3Status del_sqllist（SqList &4.5 Status DeQueue （LinkQueue &全真模拟试题（一）一、单项选择题（在每小题的4个备选答案中，选出正确的答案，并将其号码填在题干的括号内。每小题2分，共24分）1若某线性表中最常用的操作是取第i 个元素和找第i个元素的前趋元素，则采用（4）存储方式最节省时间。单链表双链表 单向循环 顺序表2串是任意有限个（1）符号构成的序列符号构成的集合字符构成的序列字符构成的集合

11、3设矩阵A（aij，li,j 10）的元素满足：aij0（ij, li, j 10）aij=0 （ij, li, j 10）现将A的所有非0元素以行序为主序存放在首地址为2000的存储区域中，每个元素占有4个单元，则元素A95的首址为23402336216421604如果以链表作为栈的存储结构，则退栈操作时（必须判别栈是否满对栈不作任何判别必须判别栈是否空判别栈元素的类型5设数组Data0.m作为循环队列SQ的存储空间，front为队头指针，rear为队尾指针，则执行出队操作的语句为（front=front+1front=（front+1）% mrear=（rear+1）%mfront=（fr

12、ont+1）%（m+1）6深度为6（根的层次为1）的二叉树至多有（）结点。64 32 31 637将含100个结点的完全二叉树从根这一层开始，每层上从左到右依次对结点编号，根结点的编号为1。编号为49的结点X的双亲编号为（24 25 23无法确定8设有一个无向图G=（V，E）和G=（V，E）如果G为G的生成树，则下面不正确的说法是（G为G 的子图G为G 的边通分量G为G的极小连通子图且V=VG为G的一个无环子图9用线性探测法查找闭散列表，可能要探测多个散列地址，这些位置上的键值（一定都是同义词 一定都不是同义词都相同不一定都是同义词10二分查找要求被查找的表是（3键值有序的链接表链接表但键值不

13、一定有序 键值有序的顺序表顺序表但键值不一定有序11当初始序列已经按键值有序，用直接插入算法对其进行排序，需要循环的次数为（n2nlog2n log2nn-112堆是一个键值序列k1,k2, kn,对i=1,2,|_n/2_|,满足（kik2ik2i+1kik2i+1k2ikik2i且kik2i+1（2i+1n）kik2i或kik2i+1（2i+1n）二、判断题（判断下列各题是否正确，正确在括号内打“V”，错的找“X”。每小题1分，共10分）双链表中至多只有一个结点的后继指针为空。（在循环队列中，front指向队列中第一个元素的前一位置，rear指向实际的队尾元素，队列为满的条件是front=

14、rear。对链表进行插入和删除操作时，不必移动结点。栈可以作为实现程序设计语言过程调用时的一种数据结构。在一个有向图的拓朴序列中，若顶点a在顶点b之前，则图中必有一条弧。）i对有向图G，如果从任一顶点出发进行一次深度优先或广度优先搜索就能访问每个顶点，则该图一定是完全图。“顺序查找法”是指在顺序表上进行查找的方法。向二叉排序树插入一个新结点时，新结点一定成为二叉排序树的一个叶子结点。（）键值序列A，C，D，E，F，E，F是一个堆。二路归并时，被归并的两个子序列中的关键字个数一定要相等。三、填空题（每空2分，共24分）设r指向单链表的最后一个结点，要在最后一个结点之后插入s所指的结点，需执行的三

15、条语句是_；r=s;r-next=null;在单链表中，指针p所指结点为最后一个结点的条件是_。设一个链栈的栈顶指针是ls，栈中结点格式为info | link ,栈空的条件是_.如果栈不为空，则退栈操作为p=ls；_；free（p）;已知一棵度为3的树有2个度为1的结点，3个度为2的结点，4个度为3的结点，则该树中有_ 个叶子的结点。树有三种常用的存储结构，即孩子链表法、孩子兄弟链表法和_ .N个顶点的连通图的生成树有_条边。一个有向图G中若有弧、和, 则在图G的拓扑序列中，顶点vi,vj和vk的相对位置为_。设表中元素的初始状态是按键值递增的，分别用堆排序、快速排序、冒泡排序和归并排序方法

16、对其进行（按递增排序），最省时间，最费时间。下面是将键值为x 的结点插入到二叉排序树中的算法，请在划线处填上适当的内容。typedef struct pnodeint key;struct pnode*left,*right;pnode;void searchinsert（int x, pnode t ）/*t为二叉排序树根结点的指针*if （p=malloc（size）;key=x;lchild=null;rchild=null;t=p; else if （xkey） searchinsert（x,t-lchild）else_;四、应用题（本题共分）1树的后根遍历方法是：若树非空则（分）（1

17、）依据次后根遍历根的各个子树，m;（2）访问根结点2.将下图的森林转换为二叉树。（分）3.下图表示一个地区的交通网，顶点表示城市，边表示连结城市间的公路，边上的权表示修建公路花费的代价。怎样选择能够沟通每个城市且总造价最省的n-1条公路，画出所有可能的方案。图7.11 遍历无向图 （a） 无向图G6（b） 深度优先搜索示例（c） G6的邻接表表示（c）表头结点4已知一个无向图的邻接表如下图所示。（本题分，每小题分）（1）画出这个图。（2） 以v1为出发点，对图进行广度优先搜索，写出所有可能的访问序列。5.设n个元素的有序表为，为一个给定的值，二分查找算法如下：int binsearch（sql

18、ist R, keytype K）j=1;h=n ;suc=0;while（j=h）&（!suc）mid =（j+h）/2;switchcase K=Rmid.key:suc=1; break;caseK j=mid+1if （suc） return（mid）;else return（0）;将上述算法中划线语句改为：h=mid.（）改动后，算法能否正常工作？请说明原因。（）若算法不能正常工作，给出一个查找序列和一个出错情况的查找键值；若能正常工作，请给出一个查找序列和查找某个键值的比较次数。（本题分，每小题分）6.有一组键值25，84，21，47，15，27，68，35，24，采用快速排序方法由小到大进行排序，请写出每趟的结果，并标明在第一趟排序过程中键值的移动情况。（本题分）五、设计题（共14分）1设棵二叉树以二叉链表为存储结构，结点结构为lchild |data |rchild 。设计一个算法，求在前根序列中处于第k个位置的结点。设某单链表的结点结构为data |next,试画出该链表的结构图，并用类语言编写算法判断该链表的元素是否是递增的。（本题分）全真模拟试题（一）参考答案一、单项选择题123 分析：按题意，矩阵A是个三角矩阵，A I,j的首地址可用下列公式计算：LOC（aij）=LOC（a11）+（k-1）*L其中K为AI,j在A中的序号k=I*（I-1）/2+j