计算机专业基础综合(数据结构)模拟试卷2

计算机专业基础综合（数据结构）模拟试卷2

(总分：70.00，做题时间：90分钟)

一、单项选择题(总题数：21，分数：42.00)

1.单项选择题1-40小题。下列每题给出的四个选项中，只有一个选项是最符合题目要求的。（分数：

2.00）__________________________________________________________________________________________ 解析：

2.栈和队列的主要区别在于( )。

（分数：2.00）

A.它们的逻辑结构不一样

B.它们的存储结构不一样

C.所包含的运算不一样

D.插入和删除运算的限定不一样√

解析：解析：栈和队列的逻辑结构都是线性的，都有顺序存储和链式存储，有可能包含的运算不一样，但不是其主要区别。任何数据结构在针对具体问题时所包含的运算都可能不同。所以正确答案是D。

3.若循环队列以数组Q[0．．m-1]作为其存储结构，变量rear。表示循环队列中的队尾元素的实际位置，其移动按rear=(rear+1)MOD m进行，变量length表示当前循环队列中的元素个数，则循环队列的队首元素的实际位置是( )。

（分数：2.00）

A.rear-length

B.(rear—length+m)MOD m

C.(rear—length+1+m)MOD m √

D.m-length

解析：解析：按照循环队列的定义，因为元素移动按照rect=(rear+1)MOD m进行，则当数组Q[m—1]存放了元素之后，下一个入队的元素将存放到Q[0]中，因此队列的首元素的实际位置是(rear—length+1+m)MOD m。

4.一个以向量V[n]存储的栈，其初始栈顶指针top为n+1，则对于x，其正确的进栈操作是( )。

（分数：2.00）

A.top=top+1；V[top]=x

B.V[top]=x；top=top+1

C.top=top-1；V[top]=x √

D.V[top]=x；top=top-1

解析：解析：此题考查的知识点是入栈的具体操作。操作时要看栈顶的地址，先取得空间，再入栈。本题栈顶为n+1，应该用减法，所以选C。D是先存入，破坏原有数据，所以错。

5.为了增加内存空间的利用率和减少溢出的可能性，两个栈可以共享一片连续的内存空间，此时应将两栈的栈底分别设在( )。

（分数：2.00）

A.内存空间的首地址

B.内存空间的尾地址

C.内存空间的两端√

D.内存空间的中间

解析：解析：两个栈共享一个内存空间时，需要把两个栈的栈底设在内存空间的两端。

6.已知输入序列为abcd，经过输出受限的双端队列后，能得到的输出序列是( )。

（分数：2.00）

A.dacb

B.cadb √

C.dbca

D.以上答案都不对

解析：解析：输出受限的双端队列是指删除限制在一端进行，而插入允许在两端进行的队列。分析选项A，输入序列为abcd，输出序列为dacb，由输出受限性质可知以da开头的结果只有dabc，选项A为错误答案。分析选项B，输入序列为abcd，输出序列为cadb，其输入输出顺序为：先在输出端输入a，然后在非输出端输入b，这时队列中的序列为ba。再在输出端输入c，这时队列中的序列为bac；输出c，再输出a；再在输出端输入d，这时队列中的序列为bd；输出d，再输出b。最后得到输出序列为cadb。分析选项C，输入序列为abcd，输出序列为dbca，由输出受限性质可知以db开头的结果只有dbac，选项C为错误答案。

7.假设一个序列1，2，3，…，n依次进栈，如果出栈的第一个元素是n，那么第i(1≤i≤n)个出栈的元素是( )。

（分数：2.00）

A.不确定

B.n-i+1 √

C.i

D.n-i

解析：解析：进栈的顺序是：1，2，…，n，且出栈的第一个元素是n，那么根据栈后进先出的特点可知，出栈的顺序依次为：n，…，2，1，那么第n一i+1个出栈元素就是第i个进栈的元素。

8.假设一个序列1，2，3，…，n依次进栈，如果第一个出栈的元素是i，那么第i个出栈的元素是( )。（分数：2.00）

A.i-j—1

B.i-j

C.j—i+1

D.不确定的√

解析：解析：此题考查的知识点是栈的后进先出特点。若输出序列的第一个元素是i，只能说明前i一1个元素均入栈，而第j个元素何时入、出栈并不能确定，所以选D。

9.已知当前栈中有n个元素，此时如果有新的元素需要执行进栈操作，但发生上溢，则由此可以判断，此栈的最大容量为( )。

（分数：2.00）

A.n-1

B.n √

C.n+1

D.n／2

解析：解析：由于栈中有n个元素是执行进栈操作，但是发生上溢，则说明此栈中最多可以包含n个数据元素，即栈的最大容量为n。

10.设有5个元素a，b，c，d，e顺序进栈，下列几个选项中，不可能的出栈序列是( )。

（分数：2.00）

A.a，b，c，d，e

B.d，e，c，b，a

C.a，c，e，b，d √

D.c，b，a，d，e

解析：解析：由进栈出栈规则可知，对于a，b，c，d，e顺序进栈的五个元素，A、B、D均为可能的出栈序列，所以选C。

11.有6个元素按6，5，4，3，2，1的顺序依次进栈，不合法的出栈序列是( )。

（分数：2.00）

A.543612

B.453126

C.346521 √

D.234156

解析：解析：此题考查的知识点是栈的后进先出特点。考查出栈序列，要保证先入栈的一定不能在后入栈的前面出栈，C选项中的6在5前入栈，5没有出栈，6却出栈了，所以不合法。其他都符合规律。所以选C。

12.有5个元素，其入栈次序为A，B，C，D，E，在各种可能的出栈次序中，以元素C；D最先出栈的次序不包括( )。

（分数：2.00）

A.CDEBA

B.CDBEA

C.CDBAE

D.CDAEB √

解析：解析：以元素C，D最先出栈的次序有三个：CDEBA、CDBEA、CDBAE。

13.对于4个元素依次进栈，可以得到( )种出栈序列。

（分数：2.00）

A.10

B.12

C.14 √

D.16

解析：解析：n4个元素，可有14种出栈序列。

14.现有两栈，其共享空间为V[1．．m]，top[i]代表第i个栈(i=1，2)栈项，栈1的底在V[1]，栈2的底在V[m]，若两栈均采用顺序存储方式存储，则栈满的条件是( )。

（分数：2.00）

A.|top[2]-top[1]|=0

B.top[1]+1=top[2] √

C.top[1]+top[2]=m

D.top[1]=top[2]

解析：解析：此题考查的知识点是入栈的具体操作。判断栈是否满要看两个栈顶是否相邻，当top[1]+1=top[2]或top[2]-1=top[1]时都表示栈满，所以选B，而A，C没有任何意义。D表示已经出现覆盖了，也是错的。

15.一个递归算法必须包括( )。

（分数：2.00）

A.递归部分

B.终止条件和递归部分√

C.迭代部分

D.终止条件和迭代部分

解析：解析：此题考查的知识点是递归算法的组成部分。一个递归算法主要包括终止条件和递归部分，所以选B。A不全面，C、D不是递归算法。

16.执行完下列语句段后，i值为( )。 int f(int x){return((x>0)?x*f(x—1)：2)：} i=f(f(1))；

（分数：2.00）

A.2

B.4 √

C.8

D.无限递归

解析：解析：此题考查的知识点是递归算法的分析。根据题意可计算f(0)=2，f(1)=2，f(2)=4，所以选B。

17.表达式a*(b+c)一d的后缀表达式是( )。

（分数：2.00）

A.abcd*+一

B.abc+*d—√

C.abc*+d—

D.一+*abcd

解析：解析：此题考查的知识点是利用栈完成表达式的中后缀转换。顺序扫描表达式，操作数顺序输出，而运算符的输出顺序根据算术运算符的优先级确定。保证栈外运算符优先级比栈内低，若高则入栈，否则出栈输出。本题中输出顺序为a输出，*进栈，(进栈，b输出，+进栈，c输出，此时)低于+，所以“+”输

出。“)”与“(”相等，出栈删除，一低于*，所以*出栈，此时输出序列为abe+*，一入栈，输出d，输出一，结束。所以选B。

18.为了处理参数及返回地址，在递归过程或函数调用时，要用一种称为( )的数据结构。

（分数：2.00）

A.队列

B.多维数组

C.栈√

D.线性表

解析：解析：此题考查的知识点是栈的应用。要处理参数及返回地址，需要后进先出规则，应选C。A是先进先出规则，B是普通的存储结构，D是普通的逻辑结构。

19.若用一个大小为6的数组来实现循环队列，且当前rear和front的值分别为0和3，当从队列中删除一个元素，再加入两个元素后，rear和front的值分别为( )。

（分数：2.00）

A.1和5

B.2和4 √

C.4和2

D.5和1

解析：解析：此题考查的知识点是队列的特征。此题考查顺序存取时的位置计算，按顺时针计算，所以删除front+1，插入rear+1，计算后rear=2，front=4，应选Bo

20.队尾已到达一维数组的最高下标，不能再插入元素，然而队中元素个数小于队列的长度，这种现象称作( )。

（分数：2.00）

A.上溢

B.下溢

C.假溢出√

D.队列满

解析：解析：用常规意义下顺序存储结构的一维数组表示队列，由于队列的性质(队尾插入和队头删除)，容易造成“假溢出”现象，即队尾已到达一维数组的高下标，不能再插入，然而队中元素个数却小于队列的长度(容量)。

21.已知有一维数组A[0,.m×n一1]，若要对应为m行、n列的矩阵，将元素A[k](0≤k＜m×n)表示成矩阵的第i行、第j列的元素(0≤i

（分数：2.00）

A.i=k／n，j=k％m

B.i=k／m，j=k％m

C.i=k／n，j=k％n √

D.i=k／m，j=k％n

解析：解析：本题是求一维数组向二维数组转化的问题。最简单的方法是把数组A的第0—n—l共n个元素放到数组B的第一行，数组A的第n一2n—1共n个元素放到数组B的第二行中，依此类推，数组A的最后n个元素放到数组B的最后一行中。求A[k]在数组B中的位置，应先确定A[k]处在哪一行，显然应该是k／n行；然后再确定处在k／n行的哪一列，显然是k％n。

二、综合应用题(总题数：14，分数：28.00)

22.综合应用题41-47小题。（分数：2.00）

__________________________________________________________________________________________ 解析：

23.简述栈、队列、循环队列的定义。

（分数：2.00）

__________________________________________________________________________________________ 正确答案：(正确答案：(1)栈是只准在一端进行插入和删除操作的线性表，允许插入和删除的一端叫栈顶，另一端叫栈底。最后插入的元素最先删除，故栈也称后进先出(LIFO)表。 (2)队列是允许在一端插入而在

另一端删除的线性表，允许插入的一端叫队尾，允许删除的一端叫队头。最先插入队的元素最先离开(删除)，故队列也常称先进先出(FIFO)表。 (3)循环队列是解决“假溢出”的一种方法。通常把一维数组看成首尾相接。在循环队列下，通常采用“牺牲一个存储单元”或“作标记”的方法解决“队满”和“队空”的判定问题。)

解析：

24.假设以I和O分别表示入栈和出栈操作，则对初态和终态均为空的栈操作可由I和O组成的序列表示。

(1)试指出判别给定序列是否合法的一般规则。(2)两个不同合法序列(对同一输入序列)能否得到相同的输出元素序列?如能得到，请举例说明。

（分数：2.00）

__________________________________________________________________________________________

正确答案：(正确答案：(1)通常有两条规则。第一是给定序列中I的个数和O的个数相等；第二是从给定序列的开始，到给定序列中的任一位置，I的个数要大于或等于O的个数。 (2)可以得到相同的输出元素序列。例如，输入元素为A，B，C，则两个输入的合法序列ABC和BAC均可得到输出元素序列ABC。对于合法序列ABC，我们使用本题约定的IOIOIO操作序列；对于合法序列BAC，我们使用IIOOIO操作序列。)

解析：

25.有5个元素，其入栈次序为A，B，C，D，E，在各种可能的出栈次序中，以元素C，D最先出栈(即C第一个且D第二个出栈)的次序有哪几个?

（分数：2.00）

__________________________________________________________________________________________

正确答案：(正确答案：3个：C，D，E，B，A；C，D，B，E，A；C，D，B，A，E。提示：此题考查的知识点是栈的后进先出特点。按题意，C先出，说明A，B已入栈，D出栈再出栈，E可以入栈就出栈，可以有序列C，D，E，B，A。也可以B先出E再入，再出，得序列C，D，B，E，A。还可以B，A都出栈后，E再入栈出栈，得序列C，D，B，A，E。只有这三种情况。)

解析：

26.为了增加内存空间的利用率和减少溢出的可能性，通常采用两个栈利用同一块存储空间的方法。通常两个栈的栈底设在内存空间的两端，而栈顶相向，迎面增长。已知有两个栈s1、s2都采用顺序栈方式，并且共享一个存储区[0～maxsize—1]。设计共享存储空间的两个栈s1、s2的入栈和出栈算法。要求： (1)

给出算法的基本设计思想。 (2)根据设计思想，采用C或C++或Java语言描述算法，关键之处给出注释；（分数：2.00）

__________________________________________________________________________________________

正确答案：(正确答案：(1)栈sl、s2共享向量空间，将两栈栈底设在向量两端。初始时，s1栈顶指针为一1，s2栈顶为maxsize。两栈顶指针相邻时为栈满。两栈顶相向，迎面增长，栈顶指针指向栈顶元素。(2)算法设计如下：#define maxsize ／／两栈共享顺序存储空间所能达到的最多元素数#define elemtp int ／／假设元素类型为整型 typedef struct{ elemtp stack[maxsize]；／／栈空间 int top[2]；／／top 为两个栈顶指针stk；stk s：／／s是如上定义的结构类型变量，为全局变量①入栈操作：int push(int i，int X){ ／／入栈操作。i为栈号，i=0表示左边的栈s1，i=1表示右／／边的栈s2，X是入栈元素。入栈成功返回1，否则返回0 if(i＜0 I I i＞1){printf(”栈号输入不对”)；exit(0)；} if(s．top[1]一s．top[0]==1){printf("栈已满＼n")：return(0); } switch(i){ case 0：s．stack[++s．top[0/]/]=X；return 1；break；case 1：s．stack[一一s．top[1/]/]=X；return 1；} } ②退栈操作：elemtp pop(int i){ if(i＜0 || i＞1){printf(”栈号输入错误＼n”)；exit(0)；} switch(i){ case 0：if(s．top[0]==一1){printf(”栈空＼n”)；return一1；} else return s．stack[s．top[0]--]； case 1：

if(s．top[1]==maxsize){printf(”栈空＼n”)；return一1；} else return s．stack[s．top[1]++]；} }) 解析：

27.一个n×n的对称矩阵，如果以行或列为主序存入内存，则其容量为多少?

（分数：2.00）

__________________________________________________________________________________________

正确答案：(正确答案：n(n+1)／2(压缩存储)或n 2(不采用压缩存储)。提示：此问题考查的知识点是数组的存放问题。对称矩阵可以只存上三角或下三角。所用空间为1，2，3，…，n之和。)

解析：

28.设有一个n×n的上三角矩阵(a ij )，将其上三角中的元素按先行后列的顺序存于数组B[m]中，使得

B[k]=a ij且k=f 1 (i)f 2 (j)+c，请推导出函数f 1、f 2和常数c，要求f 1和f 2中不含常数项。

（分数：2.00）

__________________________________________________________________________________________

正确答案：(正确答案：上三角矩阵第1行有n个元素，第i一1行有n一(i一1)+1个元素，第1行到第i—1行是等腰梯形，而第i行上第j个元素(即a ij )是第i行上第j一i+1个元素，故元素a ij在一维

数组中的存储位置(下标k)为：k=(n+(n一(i—1)+1))(i一1)／2+(j—i+1)=(2n—i+2)(i—1)／2+j-i+1 进

一步整理为：)

解析：

29.已知有一整数序列{a 1，a 2，a 3，…，a n }。栈A中只保存整数，即序列中元素为整数时允许其入栈。设计一个算法实现如下功能：用栈结构存储入栈的整数，当a i≠一1时，将a i进栈；当a i =一1时，输出栈顶整数并出栈。

（分数：2.00）

__________________________________________________________________________________________

正确答案：(正确答案：#define maxsize ／／栈空间容量void InOutS(int S[maxsize]){ int top=0：／／top为栈项指针，定义top=0时为栈空for(i=1；i＜=n；i++){ ／／n个整数序列作处理ScaRf(”％d”，&x)；／／从输入整数序列if(X!=一1) ／／读入的整数不等于一1时入栈if(top==maxsize一1){printf(”栈满＼n”)；exit(0)；} else s[++top]=x；／／x入栈 else{ ／／读入的整数等于一1时退栈

if(top==0){printf(”栈空＼n”)；exit(0)；} else printf(”出栈元素是％d＼n”，S[top一一])；} } }) 解析：

30.设结点结构为(data，link)，试用一个全局指针p和某种链接结构实现一个队列，画出示意图，并给出入队addq和出队deleq过程，要求它们的时间复杂性都是O(1)(不计new和dispose时间)。

（分数：2.00）

__________________________________________________________________________________________

正确答案：(正确答案：本题要求用链接结构实现一个队列，可用链表结构来实现。一般说，由于队列的先进先出性质，所以队列常设队头指针和队尾指针。但题目中仅给出一个“全局指针p”，且要求入队和出

队操作的时间复杂性是O(1)，因此用只设尾指针的循环链表来实现队列。(1)proc addq(var p：l。inkedlist，x：elemtp)；／／p是数据域为data、链域为link的用循环链表表示的队列的尾指针 new(s)；／／申

请新结点。假设有内存空间，否则系统给出出错信息s ↑．data：=x；s ↑．1ink：=p ↑．link；／／将s结点入队p ↑．1ink：=s；p：=s；／／尾指针p移至新的队尾endp；(2)proc deleq(Var p：linkedlist，Var x：elemtp)；／／p是数据域为data、链域为link的用循环链表表示的队列的尾指针，本算法实／／现队列元素的出队，若出队成功，返回出队元素，否则给出失败信息if(p ↑．link==p)then{writeln(”空队列”)：return(0)；} ／／带头结点的循环队列、 else{s：=p ↑．link ↑．link；／／找到队头元素p ↑．link ↑．link：=s ↑．link；／／删队头元素x：=s ↑．data；／／返回出队元素if(p==s)then p：=p ↑．link；／／队列中只有一个结点，出队后成为空队列 dispose(s)；／／回收出队元素所占存储空间 } endp；提示：上述入队算法中，因链表结构，一般不必考虑空间溢出问题，算法简单。在出队

算法中，首先要判断队列是否为空，另外，对出队元素，要判断是否因出队而成为空队。否则，可能导致

因删除出队结点而将尾指针删掉成为“悬挂变量”。)

解析：

31.判断括号是否匹配是栈的主要应用之一。设字符表达式存储在数组E[n]中，‘#’为字符表达式的结束符。给出一个算法，用于判断表达式中括号(’(’和’)’)是否配对。要求：(1)给出算法的基本设计思想。(2)根据设计思想，采用C或C++或Java语言描述算法，关键之处给出注释。

（分数：2.00）

__________________________________________________________________________________________

正确答案：(正确答案：(1)算法的基本思想：判断表达式中括号是否匹配，可通过栈，简单说是左括号时

进栈，右括号时退栈。退栈时，若栈顶元素是左括号，则新读入的右括号与栈顶左括号就可消去。如此下去，输入表达式结束时，栈为空则正确，否则括号不匹配。在读入表达式结束符'#'时，栈中若只剩'#'，表示括号全部配对成功；否则表示括号不匹配。另外，由于本题只是检查括号是否匹配，故对从表达式中

读入的不是括号的那些字符，一律未作处理。因假设栈容量足够大，因此入栈时未判断溢出。 (2)算法的设计如下： int exyx(char E[]，int n){ ／／判断表达式中圆括号是否匹配 char s[30]；／／s是一维数组，容量足够大，用作存放括号的栈 int top=0；／／top用作栈顶指针 s[top]='#'；／／'#'先入栈，用于和表达式结束符号'#'匹配 int i=0；／／字符数组E的工作指针 while(E[i]!='#') ／／逐字符处理字符表达式的数组switch(E[i]){ case’(’：s[++top]='('；i++；break；case’)’：

if(s[top]==’(’){top一一；i++；break；} else{printf(”括号不配对”)；exit(0)；} case'#'：

if(s[top]=='#'){printf(”括号配对＼n”)；return(1)：} else{printf(”括号不配对＼n”)；

return(0)；}／／括号不配对 default：i++；／／读入其他字符，不作处理 } })

解析：

32.从键盘上输入一个逆波兰表达式，用伪码写出其求值程序。规定：逆波兰表达式的长度不超过一行，以$符作为输入结束，操作数之间用空格分隔，操作符只可能有+、一、*、／四种运算，例如：234—34+2*$。（分数：2.00）

__________________________________________________________________________________________

正确答案：(正确答案：逆波兰表达式(即后缀表达式)求值规则如下：设立运算数栈OPND，对表达式从左到右扫描(读入)，当表达式中扫描到数时，压入OPND栈。当扫描到运算符时，从OPND退出两个数，进行相应运算，结果再压入OPND栈。这个过程一直进行到读出表达式结束符$，这时OPND栈中只有一个数，就是结果。 float expr(){ ／／从键盘输入逆波兰表达式，以’$’表示输入结束，本算法求逆波兰表达式的值 float OPND[30]；／／OPND是操作数栈 init(OPND)；／／两栈初始化 float num=O．0；／／数字初始化scanf(”％C”，＆x)；／／x是字符型变量while(X!=’$’){ switch(X){ case’0’：case’1’．case ’2’ case’3’：case’4’：case’5’：case’6’：case’7’：case’8’：case’9’： while((x＞=’0’&&x＜=’9’)|| x==．’)／／拼数if(x!=‘．’){num=num*10+(ord(x)一o rd(’0’))；scanf(”％C”，&x)；}／／处理整数else{ ／／处理小数部分scale=10．0；scanf(”％C”，&x)； while(x＞=’0’&&x＜=’9’){ num=num+(ord(x)-ord(’0’))／scale； scale=scale*10；scanf(”％c”，&x)：} }／／else push(OPND，hum)；hum=0．0；／／数压入栈，下个数初始化case”：break；／／遇空格，继续读下一个字符case’+’：push(OPND，pop(OPND)+pop(OPND))；break；case’-’：x1=pop(OPND)；x2=pop(OPND)；push(OPND，x2-x1)；break；case’*’：push(OPND，pop(OPND)*pop(OPND))；break；case’/’：x1=pop(OPND)；x2=pop(OPND)；push(OPND，x2／x1)；break；default：／／其他符号不作处理 }／／结束switch scanf(”％c”，&x)：／／读入表达式中下一个字符 }／／结束

while(x!=’$’) printf(”后缀表达式的值为％f”)；pop(OPND)； })

解析：

33.假设以I和O分别表示入栈和出栈操作。栈的初态和终态均为空，入栈和出栈的操作序列可表示为仅由I和O组成的序列，称可以操作的序列为合法序列，否则称为非法序列。 (1)下面所示的序列中哪些是合法的? A．IOIIOIOO B．IOOIOIIO C．IIIOIOIO D．IIIOOIOO (2)通过对(1)的分析，写出一个算法，判定所给的操作序列是否合法。若合法，返回true，否则返回false(假定被判定的操作序列已存入一维数组中)。（分数：2.00）

__________________________________________________________________________________________

正确答案：(正确答案：(1)A和D是合法序列，B和C是非法序列。(2)设被判定的操作序列已存入一维数组A中。 int Judge(char A[]){ ／／判断字符数组A中的输入／输出序列是否是合法序列。如是，返回true，／／否则返回false int i=0：／／i为下标 int j=k=0；／／j和k分别为I和字母0的个数while(A[i]!=’＼0’){ switch(A[i]){ case’I’：j++；break；／／入栈次数增1 case’0’；k++；if(k＞j){printf(”序列非法＼n”)；exit(0)；} } i++；／／不论A[i]是’I’或’0’，指针i均后移} if(j!=k){printf(”序列非法＼n”)；return(false)；} else{printf(”序列合法＼n”)；

return(true)：} } })

解析：

34.设计一个算法，判断一个算术表达式中的括号是否配对。算术表达式保存在带头结点的单循环链表中，每个结点有两个域：ch和link，其中ch域为字符类型。

（分数：2.00）

__________________________________________________________________________________________

正确答案：(正确答案：表达式中的括号有以下三对：’(’、’)’、’[’、’]、’{’、’}’，使用栈，

当为左括号时入栈，右括号时，若栈顶是其对应的左括号，则退栈，若不是其对应的左括号，则结论为括号不配对。当表达式结束，若栈为空，则结论表达式括号配对：否则，结论表达式括号不配对。 int Match(LinkedList la){ ／／算术表达式存储在以la为头结点的单循环链表中，本算法判断括号是否正确配对char S[]；／／s为字符栈，容量足够大P=la一＞link；／／p为工作指针，指向待处理结点Stack Init(S)；／／初始化栈S while(P!=la){ ／／循环到头结点为止switch(p一＞ch){ case’(’：push(s，p一＞ch)；break；case’)’：if(StackEmpty(s)IIStackGetTop(s)!=’(’){ printf(”括号不配对＼n”)；retum(0)： } else pop(S)； break；case’[’：push(s，p-＞ch)；break；case’[’：

if(StackEmpty(s)|| StackGetTop(s)!=l[’){ printf(”括号不配对＼n”)；return(0)；} else pop(S)；breaki case’{’：push(s，p-＞ch)；break；case’}’：

if(StackEmpty(s)||StackGetTop(s)!=’{’){ printf(”括号不配对＼n”)：return(0)；} else pop(S)：break； }P=p-＞link：／／后移指针 }／／while if(StackEmpty(S)){printf(”括号配对＼n”)；return(1)：} else{ printf(”括号不配对＼n”)；return(0)； } })

解析：

35.请利用两个栈s1和s2来模拟一个队列。已知栈的三个运算定义如下： (1)push(st，x)：元素x入st 栈： (2)pop(st，x)：st栈顶元素出栈，赋给变量x； (3)sempty(st)：判st栈是否为空。那么如何利用栈的运算来实现该队列的三个运算： (1)enqueue：插入一个元素入队列； (2)dequeue：删除一个元素出队列： (3)queue_empty：判队列为空。(请写明算法的思想及必要的注释。)

（分数：2.00）

__________________________________________________________________________________________

正确答案：(正确答案：栈的特点是后进先出，队列的特点是先进先出。所以，用两个栈s1和s2模拟一个队列时，s1作输入栈，逐个元素压栈，以此模拟队列元素的入队。当需要出队时，将栈s1退栈并逐个压入栈s2中，s1中最先入栈的元素，在s2中处于栈顶。s2退栈，相当于队列的出队，实现了先进先出。显然，只有栈s2为空且s1也为空，才算是队列空。 (1)int enqueue(stack s1，elemtp x){ ／／sl是容量为n的栈，栈中元素类型是elemtp。本算法将x入栈，／／若入栈成功返回1，否则返回0

if(topl==n&&!sempty(s2)) ／／topl是栈s1的栈顶指针，是全局变量{printf(”栈满”)；return(O)；} ／／sl满s2非空，这时s1不能再入栈 if(top1==n&&sempty(s2)) ／／若s2为空，先将sl退栈，元素再压栈到s2 {while(!sempty(s1)){pop(s1，x)；push(s2，X)；} push(s1，x)；return(1)；／／x入栈，实现了队列元素的入队 } (2)void dequeue(stack s2，s1){ ／／s2是输出栈，本算法将s2栈顶元素退栈，实现队列元素的出队 if(!sempty(s2)) ／／栈s2不空，则直接出队 {pop(s2，x)；printf(”出队元素为”，X)；} else ／／处理s2空栈if(sempty(s1)){printf(”队列空”)；exit(0)；} ／／若输入栈也为空，则判定队空 else ／／先将栈s1倒入s2中，再做出队操作 {while(!sempty(s1)){pop(s1，x)；push(s2，x)；} pop(s2，x)；／／s2退栈相当于队列出队printf(”出队元素”，X); } (3)int queue_empty(){ ／／本算法判用栈s1和s2模拟的队列是否为空if(sempty(s1)&&sempty(s2))return(1)；／／队列空 else return(0)；／／队列不空 })

解析：

数据结构模拟题(开卷)

《数据结构》模拟题（补） 一．单项选择题 1.在线性表的下列存储结构中，读取元素花费时间最少的是【】。 A．单链表B．双链表C．顺序表D．循环链表 2.设计一个判定表达式中左、右括号是否配对出现的算法，采用【】数据结构最佳。 A．集合B．线性表C．队列D．栈 3.n个结点的线索二叉树上含有的线索数为【】。 A．2n B．n-1 C．n D．n+1 4.设广义表D=(a,(b,c)),则tail(D）=【】。 A．b,c B．(b,c) C．((b,c)) D．c 5.由4个结点可以构造出【】种不同的二叉树。 A．12 B．13 C．14 D．15 6.在栈中，出栈操作的时间复杂度为【】。 A．O(1) B．O(n) C．O(log2n) D．O(n2) 7.假设Q[0..len-1]表示循环队列，f为队头指针，r为队尾指针，则进队操作语句是【】。 A．f=f+1 B．r=r+1 C．f=(f+1)%len D．r=(r+1)%len 8.一个n*n的对称矩阵，如果以行或列为主序放入内存，则其容量为【】。 A．n*n B．n*n/2 C．n*(n+1)/2 D．(n+1)*(n+1)/2 9.队列操作的原则是【】。 A．进优于出B．出优于进C．先进先出D．后进先出 10.下列数据结构中，【】是非线性数据结构。 A．栈B．串C．队列D．树 11.两个指针p和q，分别指向单链表的两个元素，p所指元素是q所指元素的前驱，则【】。 A．p==q B．q->next=p C．p->next=q D．p->next=q->next 12.数组A中，每个元素的长度为4个字节，行下标i从1到5，列下标j从1到4，从首 地址SA开始连续存放在存储器内，该数组按行存放时，元素A[3][2]的起始地址为【】。 A．SA+20 B．SA+36 C．SA+40 D．SA+45 13.已知一个顺序存储的线性表，设每个结点需占m个存储单元，若第一个结点的地址为d1， 则第i个结点的地址为【】。 A．d1+(i-1)*m B．d1+i*m C．d1+(i+1)m D．d1-i*m 14.分析下列算法suanfa1(n)的时间复杂度是【】。 void suanfa1(int n) { int i,j,x=1； for(i=0；i

数据结构试卷及答案2套

数据结构试卷1 一、单项选择题：(每小题2分，共20分) 1. 在一个长度为n的顺序表中顺序搜索一个值为x的元素时，在等概率的情况下，搜索成功时的数据平均比较次数为________。 A. n B. n/2 C.(n+1)/2 D.(n-1)/2 2. 不带头结点的单链表first为空的判定条件是_________。 A. first->next == NULL; B. first == NULL; C. first->next == first; D. first != NULL; 3. 栈的插入和删除操作在__________进行。 A. 栈顶 B. 栈底 C. 任意位置 D. 指定位置 4. 假定一个链式队列的队头和队尾指针分别为front和rear，则判断队空的条件为__________。 A. front==rear B. front!=NULL C. rear!=NULL D. front==NULL 5. 设有一个广义表A ( (x, (a, b) ), (x, (a, b), y) )，运算Head (Head (Tail (A) ) ) 的执行结果为________。 A．y B．(a, b) C．(x,(a,b)) D．x 6. 在一棵具有n个结点的二叉树中，所有结点的空子树个数等于_________。 A. n B. n-1 C. n+1 D. 2*n 7. 利用n个值作为叶结点的权重，生成的霍夫曼树中共包含有_________个结点。 A. n B. n+1 C. 2*n D. 2*n-1 8. 设无向图的顶点个数为n，则该图最多有________条边。 A. n-1 B. n(n-1)/2 C. n(n+1)/2 D. n(n-1) 9. 任何一个无向连通图的最小生成树_________。 A．只有一棵 B. 一棵或多棵 C. 一定有多棵 D. 可能不存在 10. 从未排序序列中依次取出一个元素与已排序序列中的元素依次进行比较，然后将其放在已排序序列的合适位置，该排序方法称为_______排序法。 A．选择B.二路归并C.交换 D.插入 二、填空题（每空1分，共20分） 1. 数据结构是一门研究非数值计算的程序设计问题中计算机的____________以及它们之间的___________和运算等的学科。 2. 顺序表中逻辑上相邻的元素的物理位置________相邻。单链表中逻辑上相邻的元素的物理位置__________相邻。 3. 在单链表中，除了首元结点外，任一结点的存储位置由___________________ 指示。 4. ________ 是被限定为只能在表的一端进行插入运算，在表的另一端进行删除运算的线性

数据结构模拟试题1

一、填空题（共20分，每空1分）。 1.数据结构是研究数据元素之间抽象化的相互关系和这种关系在计算机中的存储结构表 示，通常有下列四种存储结构：（1）、（2）、（3）和（4）。 2.评价算法的标准很多，通常是以执行算法所需要的（5）和所占用的（6）来判别一 个算法的优劣。 3.队列操作的原则是（7），栈的插入和删除操作在（8）进行。 4.对循环队列Q，它的最大存储空间是MAXSIZE，队头指针是front，队尾指针是rear， 采用少用一个存储单元的方法解决假溢出时，队满的判断条件是（9），队空的判断条件是（10）。 5.在以head 为表头指针的带有头结点的单链表和循环单链表中，判断链表为空的条件分 别为（11）和（12）。 6.假设二维数组A[6][8]，每个元素用相邻的4个字节存储，存储器按字节编址，已知 A[0][0]的存储位置为100，按行优先顺序存储的元素A[2][5]的第一个字节的地址为（13）。 7.空格串的长度为串中所包含（14）字符的个数，空串的长度为（15）。 8.有向图G 用邻接矩阵A[n][n] 存储表示，其第i 行的所有元素之和等于顶点i 的 （16）。 9.在关键字序列(12 ，23 ，34 ，45 ，56 ，67 ，78 ，89 ，91) 中折半查找 关键字为89和25的结点时，所需进行的比较次数分别为（17）和（18）。 10.请说出两种处理哈希冲突的方法（19）、_（20）_。 二、选择题（共20分，每题2分）。 1.对线性表，在下列哪种情况下应采用链式存储结构？（） A.经常需要随机存取元素 B.经常需要进行插入和删除操作 C.表中元素的个数不变 D.表中元素需要占据一片连续的存储空间 2.从一个具有n个结点的单链表中查找其值等于x结点时，在查找成功情况下，则平均比 较（）个结点。 A.n B.n/2 C.(n-1)/2 D.(n+1)/2 3.若对某线性表最常进行的操作是在最后一个元素之后插入和删除第一个元素，则采用 （）存储方式最节省运算时间。 A.单链表 B.双链表 C.仅有头指针的单循环链表 D.仅有尾指针的单循环链表 4.在一个单链表中，若要删除p指针所指结点的后继结点，则执行（）。 A.p=p->next; p->next=p->next->next; B.p->next=p->next->next; C.p=p->next; D.p=p->next->next;

数据结构模拟试题及答案

数据结构模拟试题一 一、判断题（每小题1 分，共15分） 1.计算机程序处理的对象可分为数据和非数据两大类。 2.全体自然数按大小关系排成的序列是一个线性表。 3.在描述单向链表的结点类型时，必须首先描述数值字段，然后再描述指针字段。 4.顺序栈是一种规定了存储方法的栈。 5.树形结构中的每个结点都有一个前驱。 6.在任何一棵完全二叉树中，最多只有一个度为1的分支结点。 7.若某顶点是有向图的根，则该顶点的入度一定是零。 8.如果某图的邻接矩阵有全零的行，没有全零的列，则该图一定是有向图。 9.用一维数组表示矩阵可以节省存储空间。 10.广义表的长度与广义表中含有多少个原子元素有关。 11.分块查找的效率与线性表被分成多少块有关。 12.散列表的负载因子等于存入散列表中的结点个数。 13.在起泡排序过程中，某些元素可能会向相反的方向移动。 14.按某种逻辑关系组织起来的记录的集合称为逻辑记录。 15.索引非顺序文件的特点是索引表中的索引项不一定按关键字大小有序排列。 二、填空题（每空1分，共15分） 1.顺序表是一种_____________线性表。 2.若用Q[1]~Q[m]作为非循环顺序队列的存储空间，则对该队列最多只能执行___次插入操作。 3.栈和队列的区别在于________的不同。 4.在高度为h(h≥0)的二叉树中至少有___个结点，至多有___个结点。 5.若用二叉链表来存储具有m个叶子，n个分支结点的树，则二叉链表中有___个左指针域为空的结点，有___个右指针域 为空的结点。 6.n个顶点的有根有向图中至少有___条边，至多有___条边。 7.10行20列矩阵若用行优先顺序表来表示，则矩阵中第8行第7列元素是顺序表中第___个元素。 8.在各元素查找概率相等的情况下，用顺序查找方法从含有12个元素的有序表中查找一个元素，元素间的平均比较次数是 _____。 9.在归并两个长度为m的有序表时，排序码的比较次数至少是___次，至多是___次。 10.在高度为3的6阶B-树中，至少有___个关键字，至多有___个关键字。 三、选择题（每题2分，共30分） 1.计算机所处理的数据一般具有某种内在联系性，这是指________。 A．元素和元素之间存在某种关系B．数据和数据之间存在某种关系 C．元素内部具有某种结构D．数据项和数据项之间存在某种关系 2. 假设顺序表目前有4个元素，第i个元素放在R[i]中，1≤i≤4 。若把新插入元素存入R[6]，则________。 A．会产生运行错误B．R[1]~R[6]不构成一个顺序表 C．顺序表的长度大于顺序表元素个数，会降低存储空间利用率 D．顺序表元素序号和数组元素下标不一致，会给使用带来麻烦 3. 设H是不带表头结点循环单向链表的表头指针，P是和H同类型的变量。当P指向链表最后一个结点时，_________。A．P所指结点指针字段的值为空B．P的值与H的值相等 C．P所指结点的地址与H的值相等D．P所指结点指针字段的值与H的值相等 4. 栈的定义不涉及数据的__________。 A．逻辑结构B．存储结构C．运算D．逻辑结构和存储结构 5. 设5个元素进栈的顺序是1,2,3,4,5，则出栈的顺序有可能是___________。 A．2,4,1,3,5 B．3,4,1,5,2 C．3,2,4,1,5 D．4,1,3,2,5 6. 若某棵二叉树结点的前序序列和中序序列相同，则该二叉树_________。 A．只有一个结点B．每个结点都没有左孩子C．每个结点都没有右孩子D．不存在 7.对于一棵具有n个结点，度为3的树来说，____________。 A．树的高度至多是n-3 B．树的高度至多是n-2 C．树的最低高度是┏log3(n+1)┓ D．至少在某一层上正好有3个结点 8．n个顶点的有向图如果可以进行拓扑排序，则可以断定该有向图__________。 A．含n个强连通分量B．有唯一的入度为0的顶点C．有多个出度为0的顶点 D．是一个有根有向图 9. 特殊矩阵用行优先顺序表表示，_____________ A．简化了矩阵元素之间的逻辑关系B．便于按行处理矩阵元素

国家二级ACCESS机试选择题(数据结构与算法)模拟试卷3

国家二级ACCESS机试选择题（数据结构与算法）模拟试卷3 (总分：60.00，做题时间：90分钟) 一、选择题(总题数：30，分数：60.00) 1.在最坏情况下 （分数：2.00） A.快速排序的时间复杂度比冒泡排序的时间复杂度要小 B.快速排序的时间复杂度比希尔排序的时间复杂度要小 C.希尔排序的时间复杂度比直接插入排序的时间复杂度要小√ D.快速排序的时间复杂度与希尔排序的时间复杂度是一样的 解析：解析：按平均时间将排序分为四类：①平方阶(O(n 2 ))排序：各类简单排序，例如直接插入、直接选择和冒泡排序；②线性对数阶(O(n。log2n))排序：如快速排序、堆排序和归并排序；③O(n1+§))排序：§是介于0和1之间的常数。希尔排序便是一种；④线性阶(O(n))排序：本程序中的基数排序，此外还有桶、箱排序。 2.在深度为7的满二叉树中，度为2的结点个数为 （分数：2.00） A.64 B.63 √ C.32 D.31 解析：解析：因为在任意的二叉树中，度为O的结点(即叶子结点)总比度为2的结点的个数多1个，而度为0的结点数n 0 =2 m-1 (其中m为二叉树的深度)。本题的度为0的结点个数n 0 =2 7-1 =2 6 =64。因此，度为2的结点数n 2 =n 0 -1=63。所以选项B正确 3.设栈的顺序存储空间为S(1：m)，初始状态为top=m+1。现经过一系列入栈与退栈运算后，top=20，则当前栈中的元素个数为 （分数：2.00） A.30 B.20 C.m-19 √ D.m-20 TOP指针向上移动一位。当压入第一个元素时，TOP指针指向m+1-1=m；当压入第二个元素时，TOP指针指向 1n+1．2=m．1；…以此类推，当压入第N个元素时，TOP指针指向m+1-N=20；则N=m+1-20=m-19。因此选项C正确。 4.算法空间复杂度的度量方法是 （分数：2.00） A.算法程序的长度 B.算法所处理的数据量 C.执行算法所需要的工作单元 D.执行算法所需要的存储空间√ 解析：解析：算法空间复杂度是对一个算法在运行过程中临时占用存储空间大小的度量，因此选项D正确。 5.设循环队列为Q(1：m)，其初始状态为front=rear=m。经过一系列入队与退队运算后，front=15，rear=20。现要在该循环队列中寻找最大值的元素，最坏情况下需要比较的次数为 （分数：2.00） A.4 √ B.6 C.m-5

计算机专业基础综合(数据结构)模拟试卷1

计算机专业基础综合（数据结构）模拟试卷1 (总分：72.00，做题时间：90分钟) 一、单项选择题(总题数：21，分数：42.00) 1.单项选择题1-40小题。下列每题给出的四个选项中，只有一个选项是最符合题目要求的。（分数： 2.00）__________________________________________________________________________________________ 解析： 2.若某线性表中最常用的操作是在最后一个结点之后插入一个结点和删除第一个结点，则下面最节省运算时间的存储方式是( )。 （分数：2.00） A.单链表 B.带有头指针的单循环链表 C.双链表 D.带有尾指针的单循环链表√ 解析：解析：在链表中的最后一个结点之后插入一个结点要知道终端结点的地址，所以，单链表、带有头指针的单循环链表、双链表都不合适。考虑在带有尾指针的单循环链表中删除第一个结点，其时间性能是O(1)，所以答案是D。 3.已知两个长度分别为l和s的降序链表，若将它们合并为一个长度为l+s的升序链表，则最坏情况下的时间复杂度是( )。 （分数：2.00） A.O(l) B.O(ls) C.O(min(l，s)) D.O(max(l，s)) √ 解析：解析：在合并过程中，最坏的情况是两个链表中的元素依次进行比较，比较的次数最少是m和n中的最大值。 4.线性表中存放的主要是( )。 （分数：2.00） A.整型常量 B.字符 C.数据元素√ D.信息元素 解析：解析：线性表中主要存放的是数据元素，而数据元素可以是整型也可以是字符型，但对于一个线性表来说，所有的数据元素的类型必须相同。 5.下面的叙述中正确的是( )。 I．线性表在链式存储时，查找第i个元素的时间同i的值成正比Ⅱ．线性表在链式存储时，查找第i个元素的时间同i的值无关Ⅲ．线性表在顺序存储时，查找第i个元素的时间同i的值成正比 （分数：2.00） A.仅I √ B.仅Ⅱ C.仅Ⅲ D.I、Ⅱ、Ⅲ 解析：解析：在线性表链式存储结构中，查找第i个元素的时间与i的位置成正比。而在顺序存储结构中查找第i个元素的时间与i的位置无关。 6.对于某线性表来说，主要的操作是存取任一指定序号的元素和在最后进行插入运算，那么应该选择( )存储方式最节省时间。 （分数：2.00） A.顺序表√

数据结构模拟试题1

一、单项选择题（在每小题列出的四个选项中只有一个选项是符合题目要求的，请将正确选项前的字母填在题后的括号内。每小题2分，共40分） 1、串的长度是（）。 A、串中不同字母的个数 B、串中不同字符的个数 C、串中所含字符的个数，且大于0 D、串中所含字符的个数 2、若用数组S[1..n]作为两个栈S1和S2的共同存储结构，对任何一个栈，只有当S全满时才不能作入栈操作。为这两个栈分配空间的最佳方案是（）。 A、S1的栈底位置为0，S2的栈底位置为n+1 B、S1的栈底位置为0，S2的栈底位置为n/2 C、S1的栈底位置为1，S2的栈底位置为n D、S1的栈底位置为1，S2的栈底位置为n/2 3、队列操作的原则是（）。 A、先进先出 B、后进先出 C、只能进行插入 D、只能进行删除 4、有64个结点的完全二叉树的深度为（）（根的层次为1）。 A、8 B、7 C、6 D、5 5、在有n个结点的二叉链表中，值为非空的链域的个数为（）。 A、n-1 B、2n-1

C、n+1 D、2n+1 6、带权有向图G用邻接矩阵A存储，则顶点i的人度等于A中（）。 A、第i行非∞的元素之和 B、第i列非∞的元素之和 C、第i行非∞且非0的元素个数 D、第i列非∞且非0的元素个数 7、在有n个结点且为完全二叉树的二叉排序树中查找一个键值，其平均比较次数的数量级为（）。 A、0(n) B、0(log2n) C、0(nolg2n) D、0(n2) 8、若表R在排序前已按键值递增顺序排列，则（）算法的比较次数最少。 A、直接插入排序 B、快速排序 C、归并排序 D、选择排序 9、下列排序算法中，（）排序在某趟结束后不一定选出一个元素放到其最终的位置上。 A、选择 B、冒泡 C、归并 D、堆

《数据结构C》模拟试题

山东科技大学继续教育学院 《数据结构C》模拟试题一 班级姓名学号 一、选择题（20分） 1. 组成数据的基本单位是( )。 (A) 数据项(B)数据类型(C)数据元素(D)数据变量 2. 线性表的链接实现有利于( )运算。 (A) 插入(B)读表元(C)查找(D)定位 3. 串的逻辑结构与( )的逻辑结构不同。 (A) 线性表(B)栈(C)队列(D)树 4. 二叉树第i（i≥1）层最多有( )个结点。 (A) 2i(B)2i (C) 2i-1(D) 2i-1 5. 设单链表中p指向结点A，若要删除A后结点（若存在），则需要修改p的操作为( ) (A) p.Next = p.Next.Next (B)p=p.Next (C)p=p.Next.Next (D)p.Next=p 6. 设一数列的输入顺序为1,2,3,4,5,6，通过栈操作不可能排成的输出序列为( ) (A) 3,2,5,6,4,1 (B) 1,5,4,6,2,3 (C) 2,4,3,5,1,6 (D) 4,5,3,6,2,1 7. 设字符串S1=’ABCDEFG’，S2=’PQRST’，则运算S=CONCAT(SUB(S1,2,LENGTH(S2))，SUB(S1,LENGTH(S2),2))的结果为( ) (A) ‘BCQR’ (B) ‘BCDEF’ (C) ’BCDEFG’ (D) ‘BCDEFEF’ 8. 有一个10阶的对称矩阵A,采用压缩存储方式，以行序为主存储，a11为第一元素，其存储地址为1，每个元素占1个地址空间，则a85地址为( ) (A)13 (B) 33 (C) 18 (D) 40 9. 如果结点A有3个兄弟，而且B为A的双亲，则B的度为( ) (A) 3 (B) 4 (C) 5 (D) 1 10. 线索化二叉树中某结点D没有左孩子的必要条件是( ) (A) D.Lchild=null (B) D.ltag=1 (C) D.Rchild=null (D) D.ltag=0 二、填空题（20分） 1. 对于一个以顺序实现的循环队列Q[0..m_1]，队头、队尾指针分别为f,r,其判空的条件是 ，判满的条件是。 2. 循环链表的主要优点是。 3. 给定一个整数集合{3,5,6,9,12}，画出其对应的一棵Huffman树。 4 双向循环链表中，在p所指的结点之后插入f所指的结点，其操作为。 5. 下列为朴素的模式匹配算法，请在算法的处填入正确的子句。

《数据结构》模拟试卷一及答案

模拟试卷一 一、单选题（每题 2 分，共20分） 1.以下数据结构中哪一个是线性结构？( ) A. 有向图 B. 队列 C. 线索二叉树 D. B树 2.在一个单链表HL中，若要在当前由指针p指向的结点后面插入一个由q指向的结点， 则执行如下( )语句序列。 A. p=q; p->next=q; B. p->next=q; q->next=p; C. p->next=q->next; p=q; D. q->next=p->next; p->next=q; 3.以下哪一个不是队列的基本运算？（） A. 在队列第i个元素之后插入一个元素 B. 从队头删除一个元素 C. 判断一个队列是否为空 D.读取队头元素的值 4.字符A、B、C依次进入一个栈，按出栈的先后顺序组成不同的字符串，至多可以组成 ( )个不同的字符串？ A.14 B.5 C.6 D.8 5.由权值分别为3,8,6,2的叶子生成一棵哈夫曼树，它的带权路径长度为( )。 A． 11 B.35 C. 19 D. 53 图一 6.该二叉树结点的前序遍历的序列为( )。 A.E、G、F、A、C、D、B B. E、A、G、C、F、B、D C. E、A、C、B、D、G、F D. E、G、A、C、D、F、B 7.该二叉树结点的中序遍历的序列为( )。 A. A、B、C、D、E、G、F B. E、A、G、C、F、B、D C. E、A、C、B、D、G、F D. B、D、C、A、F、G、E 8.该二叉树的按层遍历的序列为( )。 A．E、G、F、A、C、D、B B. E、A、C、B、D、G、F C. E、A、G、C、F、B、D D. E、G、A、C、D、F、B 9.下面关于图的存储的叙述中正确的是( )。 A．用邻接表法存储图，占用的存储空间大小只与图中边数有关，而与结点个数无关B．用邻接表法存储图，占用的存储空间大小与图中边数和结点个数都有关 C. 用邻接矩阵法存储图，占用的存储空间大小与图中结点个数和边数都有关 D．用邻接矩阵法存储图，占用的存储空间大小只与图中边数有关，而与结点个数无关10.设有关键码序列(q，g，m，z，a，n，p，x，h)，下面哪一个序列是从上述序列出发建 堆的结果?( )

数据结构与算法 模拟试卷三四及参考答案

模拟试卷三 一、单选题（每题 2 分，共20分） 1.对一个算法的评价，不包括如下（）方面的内容。 A．健壮性和可读性B．并行性C．正确性D．时空复杂度 2.在带有头结点的单链表HL中，要向表头插入一个由指针p指向的结点，则执行( )。 A. p->next=HL->next; HL->next=p; B. p->next=HL; HL=p; C. p->next=HL; p=HL; D. HL=p; p->next=HL; 3.对线性表，在下列哪种情况下应当采用链表表示？( ) A.经常需要随机地存取元素 B.经常需要进行插入和删除操作 C.表中元素需要占据一片连续的存储空间 D.表中元素的个数不变 4.一个栈的输入序列为1 2 3，则下列序列中不可能是栈的输出序列的是( ) A. 2 3 1 B. 3 2 1 C. 3 1 2 D. 1 2 3 5.AOV网是一种（）。 A．有向图B．无向图C．无向无环图D．有向无环图 6.采用开放定址法处理散列表的冲突时，其平均查找长度（）。 A．低于链接法处理冲突 B. 高于链接法处理冲突 C．与链接法处理冲突相同D．高于二分查找 7.若需要利用形参直接访问实参时，应将形参变量说明为（）参数。 A．值B．函数C．指针D．引用 8.在稀疏矩阵的带行指针向量的链接存储中，每个单链表中的结点都具有相同的（）。 A．行号B．列号C．元素值D．非零元素个数 9.快速排序在最坏情况下的时间复杂度为（）。 A．O(log2n) B．O(nlog2n) C．0(n) D．0(n2) 10.从二叉搜索树中查找一个元素时，其时间复杂度大致为( )。 A. O(n) B. O(1) C. O(log2n) D. O(n2) 二、运算题（每题 6 分，共24分） 1.数据结构是指数据及其相互之间的______________。当结点之间存在M对N（M：N） 的联系时，称这种结构为_____________________。 2.队列的插入操作是在队列的_________进行，删除操作是在队列的__________进行。 3.当用长度为N的数组顺序存储一个栈时，假定用top==N表示栈空，则表示栈满的条件 是_____________________。 4.对于一个长度为n的单链存储的线性表，在表头插入元素的时间复杂度为_________， 在表尾插入元素的时间复杂度为____________。 5.设W为一个二维数组，其每个数据元素占用4个字节，行下标i从0到7 ，列下标j 从0到3 ，则二维数组W的数据元素共占用＿_____＿个字节。W中第6 行的元素和第4 列的元素共占用＿_______＿个字节。若按行顺序存放二维数组W，其起始地址为100，则二维数组元素W[6，3]的起始地址为＿________＿。 6.广义表A= (a,(a,b),((a,b),c)),则它的深度为____________，它的长度为____________。 7.二叉树是指度为2的____________________树。一棵结点数为N的二叉树，其所有结 点的度的总和是_____________。 8.对一棵二叉搜索树进行中序遍历时，得到的结点序列是一个______________。对一棵由 算术表达式组成的二叉语法树进行后序遍历得到的结点序列是该算术表达式的

数据结构模拟考试试卷2

数据结构模拟考试试卷(2卷) 一．判断题（下列各题，正确的请在前面的括号内打√；错误的打×） （√）1.数据的逻辑结构是独立于计算机的。 （×）2.在单链表中，要取得某个元素，只要知道该元素的指针即可，因此单链表是随机存取的存储结构。 （√）3.栈的特点是“后进先出”。 （√）4.判断顺序队列为空的标准是头指针和尾指针均指向同一个结点。 （×）5.串的堆分配存储是一种静态存储结构。 （×）6.完全二叉树一定是满二查树。 （×）7.邻接表只能用于有向图的存储。 （×）8.选择好的哈希函数就可以避免冲突的发生。 n)。 （√）9.对于n个记录的集合进行归并排序，所需的平均时间为O (nlog 2 （×）10.对于满足二分查找和分块查找条件的文件而言，无论它存放在何种介质上，均能进行顺序查找，折半查找和分块查找。 二．填空题 1．数据结构是一门研究非数值计算程序设计中计算机的操作对象以及它们之间的关系和运算的学科。 2．数据的存储结构形式包括：顺序存储、链式存储、散列存储、索引存储。3．在线性表的顺序存储中，元素之间的逻辑关系是通过相邻位置决定的。 4．在双向链表中，每个结点都有两个指针域，它们一个指向其前趋结点，另一个指向其后继结点。 5．在有n个元素的栈中，出栈操作的时间复杂度为 O（1）。 6．在栈结构中，允许插入、删除的一端称为栈顶。 7．对于队列，只能在队首删除元素。 8．循环队列SQ经过InitQueue (SQ)，SQ->front等于0 。 9．空格串的长度等于空格的个数。 10．设目标T="abccdcdccbaa"，模式P="cdcc"，则第 6 次匹配成功。11．采用二叉链表存储的n个结点的二叉树，一共有2n 个指针域。 12．给定如下图所示的二叉树，其前序遍历序列为：ABEFHCG 。Array 13．图的逆邻接表存储结构只适用于 __有向____图。 14．一个图的生成树的顶点是图的 _ 全部____顶点。

数据结构模拟试题一及答案汇编

学习-----好资料 数据结构模拟试题一 一、判断题（每小题1 分，共15分） 1.计算机程序处理的对象可分为数据和非数据两大类。 2.全体自然数按大小关系排成的序列是一个线性表。 3.在描述单向链表的结点类型时，必须首先描述数值字段，然后再描述指针字段。 4.顺序栈是一种规定了存储方法的栈。 5.树形结构中的每个结点都有一个前驱。 6.在任何一棵完全二叉树中，最多只有一个度为1的分支结点。 7.若某顶点是有向图的根，则该顶点的入度一定是零。 8.如果某图的邻接矩阵有全零的行，没有全零的列，则该图一定是有向图。 9.用一维数组表示矩阵可以节省存储空间。 10.广义表的长度与广义表中含有多少个原子元素有关。 11.分块查找的效率与线性表被分成多少块有关。 12.散列表的负载因子等于存入散列表中的结点个数。 13.在起泡排序过程中，某些元素可能会向相反的方向移动。 14.按某种逻辑关系组织起来的记录的集合称为逻辑记录。 15.索引非顺序文件的特点是索引表中的索引项不一定按关键字大小有序排列。 二、填空题（每空1分，共15分） 1.顺序表是一种_____________线性表。 2.若用Q[1]~Q[m]作为非循环顺序队列的存储空间，则对该队列最多只能执行___次插入操作。 3.栈和队列的区别在于________的不同。 4.在高度为h(h≥0)的二叉树中至少有___个结点，至多有___个结点。 5.若用二叉链表来存储具有m个叶子，n个分支结点的树，则二叉链表中有___个左指针域为空的结点，有___个右指针域为空的结点。 6.n个顶点的有根有向图中至少有___条边，至多有___条边。 7.10行20列矩阵若用行优先顺序表来表示，则矩阵中第8行第7列元素是顺序表中第___个元素。 8.在各元素查找概率相等的情况下，用顺序查找方法从含有12个元素的有序表中查找一个元素，元素间的平均比较次数是_____。 9.在归并两个长度为m的有序表时，排序码的比较次数至少是___次，至多是___次。 10.在高度为3的6阶B-树中，至少有___个关键字，至多有___个关键字。 三、选择题（每题2分，共30分） 1.计算机所处理的数据一般具有某种内在联系性，这是指________。 A．元素和元素之间存在某种关系B．数据和数据之间存在某种关系 C．元素内部具有某种结构D．数据项和数据项之间存在某种关系 2. 假设顺序表目前有4个元素，第i个元素放在R[i]中，1≤i≤4 。若把新插入元素存入R[6]，则________。 A．会产生运行错误B．R[1]~R[6]不构成一个顺序表 C．顺序表的长度大于顺序表元素个数，会降低存储空间利用率 D．顺序表元素序号和数组元素下标不一致，会给使用带来麻烦 3. 设H是不带表头结点循环单向链表的表头指针，P是和H同类型的变量。当P指向链表最后

数据结构模拟卷(含答案)经典习题

练习题 一、单项选择题 1. 若将数据结构形式定义为二元组(K，R)，其中K是数据元素的有限集合，则R是K上( ) A. 操作的有限集合 B. 映象的有限集合 C. 类型的有限集合 D. 关系的有限集合 2. 在长度为n的顺序表中删除第i个元素(1≤i≤n)时，元素移动的次数为( ) A. n-i+1 B. i C. i+1 D. n-i 3. 若不带头结点的单链表的指针为head，则该链表为空的判定条件是( ) A. head==NULL B. head->next==NULL C. head!=NULL D. head->next==head 4. 引起循环队列队头位置发生变化的操作是( ) A. 出队 B. 入队 C. 取队头元素 D. 取队尾元素 5. 若进栈序列为1，2，3，4，5，6，且进栈和出栈可以穿插进行，则不．可能出现的出栈序列是( ) A. 2，4，3，1，5，6 B. 3，2，4，1，6，5 C. 4，3，2，1，5，6 D. 2，3，5，1，6，4 1

6. 字符串通常采用的两种存储方式是( ) A. 散列存储和索引存储 B. 索引存储和链式存储 C. 顺序存储和链式存储 D. 散列存储和顺序存储 7. 数据结构是（） A．一种数据类型 B．数据的存储结构 C．一组性质相同的数据元素的集合 D．相互之间存在一种或多种特定关系的数据元素的集合 8. 算法分析的目的是（） A．辨别数据结构的合理性 B．评价算法的效率 C．研究算法中输入与输出的关系 D．鉴别算法的可读性 9. 在线性表的下列运算中，不．改变数据元素之间结构关系的运算是 （） A．插入B．删除 C．排序D．定位 10. 下列图示的顺序存储结构表示的二叉树是( ) 2

数据结构模拟试卷(含答案)

数据结构设计课程代码：7399 一、单项选择题（在每小题列出的四个选项中只有一个选项是符合题目要求的，请将正确选项前的字母填在题后的括号内。每小题2分，共40分） 1、串的长度是（）。 A、串中不同字母的个数 B、串中不同字符的个数 C、串中所含字符的个数，且大于0 D、串中所含字符的个数 2、若用数组S[1..n]作为两个栈S1和S2的共同存储结构，对任何一个栈，只有当S全满时才不能作入栈操作。为这两个栈分配空间的最佳方案是（）。 A、S1的栈底位置为0，S2的栈底位置为n+1 B、S1的栈底位置为0，S2的栈底位置为n/2 C、S1的栈底位置为1，S2的栈底位置为n D、S1的栈底位置为1，S2的栈底位置为n/2 3、队列操作的原则是（）。 A、先进先出 B、后进先出 C、只能进行插入 D、只能进行删除 4、有64个结点的完全二叉树的深度为（）（根的层次为1）。 A、8 B、7 C、6 D、5 5、在有n个结点的二叉链表中，值为非空的链域的个数为（）。

A、n-1 B、2n-1 C、n+1 D、2n+1 6、带权有向图G用邻接矩阵A存储，则顶点i的人度等于A中（）。 A、第i行非∞的元素之和 B、第i列非∞的元素之和 C、第i行非∞且非0的元素个数 D、第i列非∞且非0的元素个数 7、在有n个结点且为完全二叉树的二叉排序树中查找一个键值，其平均比较次数的数量级为（）。 A、0(n) B、0(log2n) C、0(nolg2n) D、0(n2) 8、若表R在排序前已按键值递增顺序排列，则（）算法的比较次数最少。 A、直接插入排序 B、快速排序 C、归并排序 D、选择排序 9、下列排序算法中，（）排序在某趟结束后不一定选出一个元素放到其最终的位置上。 A、选择 B、冒泡 C、归并 D、堆

数据结构模拟题1

模拟题 一．单项选择题 1. 如图所示的4棵二叉树中，哪一个是平衡二叉树 A. B. C. D. 2. 若一个算法的语句频度之和为T(n)=3n+ nlog2n + n2,则算法的时间复杂度为。 A. nlog2n + n2 D.nlog2n 3. 插入和删除操作只能在同一端进行的线性表，成为。 A.队列 B.循环队列 C.栈 D.循环栈 4. 一棵树Tr转换成相应的二叉树Bt，那么对Tr的后序遍历是对Bt的。 A．先序遍历B．中序遍历C．后序遍历D．无法确定 5. 判定一个循环队列Q（最多元素为m0）为空的条件是。 A．= =Q. Rear B. = =( + 1 ) % m0 C．!= D. != ( Q . rear +1 ) % m0 6. 广义表(（a,b,( ),c),(d,(e))，（）)的长度是。 .4 C 7. 在一个无向图中，所有顶点的度数之和，是其所有边数之和的倍。 A．1/2 B．1 C．2 D．4 8. tail（head（（a，b），c，（c，d）））的结果是。 A．b B．（b）C．（a，b）D．（c，d） 9. 深度为k的满二叉树有个分支 ．．结点。 -2 C +1 10.一棵有n个结点的树，在把它转换成对应的二叉树之后，该二叉树根结点的左子树上共有个结点。 A．n-2 B．n-1 C．n+1 D．n+2 11. n个顶点的带权无向连通图的最小生成树包含条边。 2 +1 12. 如图，若从顶点a出发按广度优先法进行遍历，可能得到的一种顶点序列是。 A．abcedf B．abcefd C．aebcfd D．acfdeb 13. 无向图的邻接矩阵是矩阵。 A.对称 B.上三角 C.下三角 D.稀疏 14.一个无向连通网图的最小生成树。 A．可能不存在B．只有一棵C．一定有多棵D．有一棵或多棵 15. 在下面给出的各种排序算法中，只有是稳定排序算法。 A．堆排序B．快速排序C．直接选择排序D．冒泡排序

数据结构期末模拟试题05(有答案)

课程测试试题（卷） ----------------------以下为教师填写-------------------- I、命题院（部）：数学与计算机科学学院 II、课程名称：数据结构 III、测试学期：20 －20 学年度第学期 IV、测试对象：学院专业级班 V、问卷页数（A4）：页 VI、答卷页数（A4）：页 VII、考试方式：闭卷（开卷、闭卷或课程小论文，请填写清楚） VIII、问卷内容：（请老师在出题时安排紧凑，填空题象征性的留出一点空格，学生将所有的答案做在答题纸上的规定位置，并写清楚大题、小题的题号） 一、单选题（每题 2 分，共20分） 1.以下数据结构中哪一个是线性结构？( ) A. 有向图 B. 队列 C. 线索二叉树 D. B树 2.在一个单链表HL中，若要在当前由指针p指向的结点后面插入一个由q指 向的结点，则执行如下( )语句序列。 A. p=q; p->next=q; B. p->next=q; q->next=p; C. p->next=q->next; p=q; D. q->next=p->next; p->next=q; 3.以下哪一个不是队列的基本运算？（） A. 在队列第i个元素之后插入一个元素 B. 从队头删除一个元素 C. 判断一个队列是否为空 D.读取队头元素的值 4.字符A、B、C依次进入一个栈，按出栈的先后顺序组成不同的字符串，至多 可以组成( )个不同的字符串？ A.14 B.5 C.6 D.8 5.由权值分别为3,8,6,2的叶子生成一棵哈夫曼树，它的带权路径长度为 ( )。

以下6-8题基于图1。 6.该二叉树结点的前序遍历的序列为( )。 A.E、G、F、A、C、D、B B.E、A、G、C、F、B、D C.E、A、C、B、D、G、F D.E、G、A、C、D、F、B 7.该二叉树结点的中序遍历的序列为( )。 A. A、B、C、D、E、G、F B. E、A、G、C、F、B、D C. E、A、C、B、D、G、F E.B、D、C、A、F、G、E 8.该二叉树的按层遍历的序列为( )。 A．E、G、F、A、C、D、B B. E、A、C、B、D、G、F C. E、A、G、C、F、B、D D. E、G、A、C、D、F、B 9.下面关于图的存储的叙述中正确的是( )。 A．用邻接表法存储图，占用的存储空间大小只与图中边数有关，而与结点个数无关 B．用邻接表法存储图，占用的存储空间大小与图中边数和结点个数都有关 C. 用邻接矩阵法存储图，占用的存储空间大小与图中结点个数和边数都有关 D．用邻接矩阵法存储图，占用的存储空间大小只与图中边数有关，而与结点个数无关 10.设有关键码序列(q，g，m，z，a，n，p，x，h)，下面哪一个序列是从上述 序列出发建堆的结果?( ) A. a，g，h，m，n，p，q，x，z B. a，g，m，h，q，n，p，x，z C. g，m，q，a，n，p，x，h，z D. h，g，m，p，a，n，q，x，z 二、填空题（每空1分，共26分） 1.数据的物理结构被分为_________、________、__________和___________四 种。 2.对于一个长度为n的顺序存储的线性表，在表头插入元素的时间复杂度为 _________，在表尾插入元素的时间复杂度为____________。 3.向一个由HS指向的链栈中插入一个结点时p时，需要执行的操作是 ________________;删除一个结点时，需要执行的操作是 ______________________________（假设栈不空而且无需回收被删除结点）。

2009年全国自考数据结构模拟试卷(一)及答案

2009年全国自考数据结构模拟试卷(一) 一、单项选择题(本大题共15小题,每小题2分,共30分)在每小题列出的四个备选项目中只有一个是符号题目要求的,请将其代码填写的括号内.错选、多选或未选均无分。 1. 任何一个带权的无向连通图的最小生成树() A. 只有一棵 B. 有一棵或多棵 C. 一定有多棵 D. 可能不存在 答案：B 2. Aarr和Barr两个数组的说明如下： VARAarr:Array［0··7］of char; Barr:Array［-5··2,3,··8］of char; 这两个数组分别能存放的字符的最大个数是() A. 7和35 B. 1和5 C. 8和48 D. 1和6 答案：C 3. 下列说法中正确的是() A. 任何一棵二叉树中至少有一个结点的度为2 B. 任何一棵二叉树中的每个结点的度为2 C. 任何一棵二叉树中的度肯定等于2 D. 任何一棵二叉树中的度可以小于2 答案：D 4. 二分查找算法要求被查找的表是() A. 键值有序的链表 B. 键值不一定有序的链表 C. 键值有序的顺序表 D. 键值不一定有序的顺序表 答案：C 5. 设图G采用邻接表存储，则拓扑排序算法的时间复杂度为() A. O(n) B. O(n+e) C. O(n2) D. O(n×e)

答案：B 6. 设数组data［0..m］作为循环队列SQ的存储空间，front为队头指针，rear为队尾指针，则执行出队操作的语句为() A. front:＝front+1 B. front:＝(front+1)mod m C. rear:＝(rear+1)mod m D. front:＝(front+1)mod (m+1) 答案：D 7. 设串s1=′ABCDEFG′,s2=′PQRST′,函数con(x,y)返回x和y串的连(s,i,j)返回串s的从序号i的字符开始的j个字符组成的子串，len(s)返回串s的 con(subs(s1,2,len(s2)),subs(s1,len(s2),2)的结果串是() A. BCDEF B. BCDEFG C. BCPQRST D. BCDEFEF 答案：D 8. 设二叉树根结点的层次为0，一棵高度为h的满二叉树中的结点个数是() A. A B. B C. C D. D 答案：D 9. 森林T中有4棵树 ，第一、二、三、四棵树的结点个数分别是n1,n2,n3,n4，那么当把森林T转换成一棵二叉树后，其根结点的左孩子上有() 个结点。 A. n1-1 B. n1 C. n1+n2+n3 D. n2+n3+n4 答案：A 10. 对广义表((a),(b))进行下面的操作head(head((a),(b)))后的结果是() A. a B. (a)