1、计算机学科专业基础综合数据结构-3 及答案解析(总分：100.00，做题时间：90 分钟)一、单项选择题(总题数：20，分数：54.00)在做进栈运算时，应先判别栈是否 () ，在做退栈运算时应先判别栈是否 () 。当栈中元素为 n 个，做进栈运算时发生上溢，则说明该栈的最大容量为 () 。为了增加内存空间的利用率和减少溢出的可能性，由两个栈共享一片连续的内存空间时，应将两栈的 () 分别设在这片内存空间的两端，这样，当 () 时，才产生上溢。（分数：10.00）A空B满C.上溢D.下溢A空B满C.上溢D.下溢A.n-1BnC.n+1D.n/2A.长度B.深度C.栈顶D.栈底A.两个栈的栈顶同
2、时到达栈空间的中心点B.其中一个栈的栈顶到达栈空间的中心点C.两个栈的栈顶在栈空间的某一位置相遇D.两个栈均不空，且一个栈的栈顶到达另一个栈的栈底1.设 abcdef 以所给的次序进栈，若在进栈操作时，允许退栈操作，则下面得不到的序列为_。（分数：2.00）A.fedcbaB.bcafedC.dcefbaD.cabdef2.栈在_中应用。（分数：2.00）A.递归调用B.子程序调用C.表达式求值D.以上都是3.表达式 a*(b+c)-d 的后缀表达式是_。（分数：2.00）A.abcd*+-B.abc+*d-C.abc*+d-D.-+*abcd4.用链接方式存储的队列，在进行删除运算时_。（分
3、数：2.00）A.仅修改头指针B.仅修改尾指针C.头、尾指针都要修改D.头、尾指针可能都要修改5.设 A 是 nn 的对称矩阵，将 A 的对角线及对角线上方的元素以列为主的次序存放在一维数组B1n(n+1)/2中，对上述任一元素 a ij (1i，jn，且 ij)在 B 中的位置为_。（分数：2.00）A.i(i-1)/2+jB.j(j-1)/2+iC.j(j-1)/2+i-1D.i(i-1)/2+j-16.对稀疏矩阵进行压缩存储的目的是_。（分数：2.00）A.便于进行矩阵运算B.便于输入和输出C.节省存储空间D.降低运算的时间复杂度7.已知有一维数组0mn-1，若要对应为 m 行 n 列的
4、矩阵，将元素 Ak(0kmn)表示成矩阵的第i 行、第 j 列的元素(0im，0jn)，则下面的对应关系是_。（分数：2.00）A.i=k/n，j=k%mB.i=k/m，j=k%mC.i=k/n，j=k%nD.i=k/m，j=k%n8.将递归算法转换成对应的非递归算法时，除了单向递归和尾递归的情况外，通常用来保存中间结果的是_。（分数：2.00）A.链表B栈C.队列D.顺序表9.在下列选项中不使用栈的是_。（分数：2.00）A.解释器B.Web 浏览器C.文本编辑器D.缓冲区10.假设一个循环队列 Q maxSize的队头指针为 front，队尾指针为 rear，队列的最大容量为 maxSiz
5、e，除此之外，该队列再没有其他数据成员，则该队列的队满条件是_。（分数：2.00）AQBQCQDQ11.在一个二维数组 A 中，假设每个数组元素的长度为 3 个存储单元，行下标 i 从 0 到 8，列下标 j 从 0到 9，从首地址 SA 开始按行连续存放。在这种情况下，元素 A85的起始地址为_。（分数：2.00）A.SA+141B.SA+144C.SA+222D.SA+25512.用 S 表示进栈操作，用 X 表示出栈操作，若元素的进栈顺序是 1234，为了得到 1342 的出栈顺序，相应的 S 和 X 的操作序列为_。（分数：2.00）A.SXSXSSXXB.SSSXXSXXC.SXSS
6、XXSXD.SXSSXSXX13.假设一个栈的输入序列是 1，2，3，4，则不可能得到的输出序列是_。（分数：2.00）A.1，2，3，4B.4，1，2，3C.4，3，2，1D.1，3，4，2设 n 个元素的进栈序列为 1，2，3，n，其出栈序列是 p 1 ，p 2 ，p 3 ，p n ，若 p 1 =3，则 p 2 的值为_；设 n 个元素的进栈序列为 p 1 ，p 2 ，p 3 ，p n ，其出栈序列是1，2，3，n，若 p 3 =1，则 p 1 的值为_。（分数：4.00）A.一定是 2B.可能是 2C.不可能是 2D.以上都不对A.一定是 2B.可能是 2C.不可能是 2D.以上都不对
7、14.设循环队列的存储容量为 maxSize，队头和队尾指针分别为 front 和 rear。若有一个循环队列 0，下列语句中可用来计算队列元素个数的是_。（分数：2.00）A.(QB.(QCQDQ15.假设一个循环队列 QmaxSize的队头指针为 front，队尾指针为 rear，队列的最大容量为 maxSize，除此之外，该队列再没有其他数据成员，则该队列的队满条件是_。（分数：2.00）AQBQCQDQ16.设链式栈中结点的结构为(data，link)，且 top 是指向栈顶的指针。若想在链式栈的栈顶插入一个由指针 s 所指的结点，则应执行的操作是_。（分数：2.00）A.top-li
8、nk=s;B.s-link=top-link;top-link=s;C.s-link=top;top=s;D.s-link=top;top=top-link;17.设链式栈中结点的结构为(data，link)，且 top 是指向栈顶的指针。若想摘除链式栈的栈顶结点，并将被摘除结点的值保存到 x 中，则应执行的操作是_。（分数：2.00）A.x=top-data;top=top-link;B.top=top-link;x=top-data;C.x=top;top=top-link;D.x=top-data;设有一个 1010 的堆成矩阵 A1010，采取按行压缩存储的方式存放于一个一维数组 B
9、中，则数组B 的容量应为_。若设 A00存放于 B0，且数组 A 的每一个数组元素在数组 B 中占一个数组元素位置，若按照下三角方式压缩仔放，A85在数组 B 中的位置是_；按照上 i 角方式压缩存放，A85在数组 B( )中的位置是_。（分数：6.00）A.20B.50C.55D.100A.39B.41C.43D.65A.41B.43C.49D.65二、综合应用题(总题数：8，分数：46.00)18.常用的阶乘函数定义如下： （分数：4.00）_19.定义斐波那契数列为 F 0 =0，F 1 =1，F i =Fi -1 +F i-2 ，i=2，3，n。其计算过程为 Long Fib (lon
10、g n) if (n2) return (n); else return (Fib (n-1)+Fib (n-2); 试推导求 F n 时的计算次数。 （分数：4.00）_20.试推导当总盘数为 n 时的 Hanoi 塔的移动次数。 （分数：4.00）_下面是队列 QUEUE 和栈 STACK 的主要操作： QUEUE:(设定每个队列元素的数据类型为 Type) bool isEmpty(QUEUE Q); /判断队列空否,true 为空,false 不空 bool getFront(QUEUE Q,Type /通过 x 返回队头元素的值 void enQueue(QUEUE Q,Type x
11、); /将新元素 x 插入到队列的队尾 void deQueue(Queue Q); /从队列中退出队头元素 STACK:(设定每个栈元素的数据类型与队列相同,为 Type) void initStack(STACK S); /对新创建的栈初始化,置成空栈 bool isEmpty(STACK S); /判断栈空否,true 栈空,false 不空 void push(STACK S,Type x); /将新元素 X 进栈 void pop(STACK S); /栈顶元素退栈 bool getTop(STACK S,Type /通过 x 返回栈顶元素的值 利用以上栈和队列的操作，编写以下针对队
12、列的函数的实现代码(要求非递归实现)。（分数：18.00）(1).“逆转”函数 void reverse(QUEUEB.s-link=top-link;top-link=s;C.s-link=top;top=s; D.s-link=top;top=top-link;解析：解析 链式栈的栈顶在链头，插入新结点要插在表头并修改表头指针。17.设链式栈中结点的结构为(data，link)，且 top 是指向栈顶的指针。若想摘除链式栈的栈顶结点，并将被摘除结点的值保存到 x 中，则应执行的操作是_。（分数：2.00）A.x=top-data;top=top-link; B.top=top-link;x
13、=top-data;C.x=top;top=top-link;D.x=top-data;解析：解析 从链式栈中删除的是表头结点。设有一个 1010 的堆成矩阵 A1010，采取按行压缩存储的方式存放于一个一维数组 B 中，则数组B 的容量应为_。若设 A00存放于 B0，且数组 A 的每一个数组元素在数组 B 中占一个数组元素位置，若按照下三角方式压缩仔放，A85在数组 B 中的位置是_；按照上 i 角方式压缩存放，A85在数组 B( )中的位置是_。（分数：6.00）A.20B.50C.55 D.100解析：解析 数组 B 共应有 1+2+10=55 个元素。若按照下三角形式存储，A85正好
14、在 B中， LOC(8，5)=(i+1)i/2+j=(8+1)8/2+5=41。 若按照上三角形式存储，A85不在 B中，找其对称元素 A58的存储位置： LOC(5，8)=(2n-i-1)i/2+j=(210-5-1)5/2+8=43。A.39B.41 C.43D.65解析：A.41B.43 C.49D.65解析：二、综合应用题(总题数：8，分数：46.00)18.常用的阶乘函数定义如下： （分数：4.00）_正确答案：()解析：为推导求 n!时的计算次数，可用递归方式计算。设当 n=0 时计算时间复杂度为常数 T(0)=d，当n0 时按 T(n)=T(n-1)+c(c 为常数)，则有： T
15、(n)=T(n-1)+c=T(n-2)+2c=T(n-3)+3c=T(1)+(n-1)c =T(0)+nc=nc+d19.定义斐波那契数列为 F 0 =0，F 1 =1，F i =Fi -1 +F i-2 ，i=2，3，n。其计算过程为 Long Fib (long n) if (n2) return (n); else return (Fib (n-1)+Fib (n-2); 试推导求 F n 时的计算次数。 （分数：4.00）_正确答案：()解析：为推导求 F n 时的计算，此时，以 n=5 为例，求 Fib(5)的递归树如下图所示。 20.试推导当总盘数为 n 时的 Hanoi 塔的移动
16、次数。 （分数：4.00）_正确答案：()解析：描述 Hanoi 塔问题的递归算法如下： void Hanoi (int n,char x,char y,char z) if (n=1)move(x,1,z); else Hanoi (n-1,x,z,y); move (x,1,z); Hanoi (n-1,y,x,z); 设 move()函数执行的移盘次数为常数 1，则 Hanoi 塔问题总的运算次数为： T(1)=1； T(2)=2T(1)+1=3=2 2 -1； T(3)=2T(2)+1=23+1=7=2 3 -1； T(4)=2T(3)+1=27+1=15=2 4 -1； T(n)=2
17、T(n-1)+1=2 n -1下面是队列 QUEUE 和栈 STACK 的主要操作： QUEUE:(设定每个队列元素的数据类型为 Type) bool isEmpty(QUEUE Q); /判断队列空否,true 为空,false 不空 bool getFront(QUEUE Q,Type /通过 x 返回队头元素的值 void enQueue(QUEUE Q,Type x); /将新元素 x 插入到队列的队尾 void deQueue(Queue Q); /从队列中退出队头元素 STACK:(设定每个栈元素的数据类型与队列相同,为 Type) void initStack(STACK S);
18、 /对新创建的栈初始化,置成空栈 bool isEmpty(STACK S); /判断栈空否,true 栈空,false 不空 void push(STACK S,Type x); /将新元素 X 进栈 void pop(STACK S); /栈顶元素退栈 bool getTop(STACK S,Type /通过 x 返回栈顶元素的值 利用以上栈和队列的操作，编写以下针对队列的函数的实现代码(要求非递归实现)。（分数：18.00）(1).“逆转”函数 void reverse(QUEUEinitStack (s);Type trap; while (!isEmpty(Q) getFront(Q
19、,tmp);deQueue(Q);Push(S,tmp); while (!isEmpty(S) getTop(S,tmp);Pop(S);enQueue(Q,tmp); (2).“判等”函数 bool equal(QUEUE Q1，QUEUE Q2)（分数：6.00）_正确答案：()解析：“判等”函数。本函数做判等比较，所以判断之后，原队列的内容应保持比较之前的状态，不能因判断而改变，所以函数参数表中的两个队列应是传值型参数，不应是引用型参数，Q1 和 Q2 是实际参数的副本。算法思路是：当两个队列都非空时，做对应元素比较，一旦发现不等则立即可以断定两个队列不等并退出比较，否则继续比较。当两
20、个队列经过这样的逐个元素比较后都变空且每一对应元素都相等，则两个队列相等；否则不等。 bool equal (QUEUE Q1,QUEUE Q2) Type t1,t2;bool finished=true; while (!is.Empty(Q1)deQueue(Q1); /从左队列退出一个元素 getFront(Q2,T2);deQueue(Q2); /从右队列退出一个元素 if(t1!=t2)finished=false;break; if(finished=false |!isEmpty(Q1)|!isEmpty(Q2)return false; else return true; (
21、3).“清空”函数 void clear(QUEUE 21.借助栈实现带表头结点的单链表上的逆置运算。 （分数：4.00）_正确答案：()解析：由于进栈与出栈顺序正好相反，因此，借助栈可以实现单链表的逆置运算。方法是让单链表中的结点依次进栈，再依次出栈。 void invert(LinkList LinkedNode * p=L-link, * q; while (p!=NULL) push(s,p);p=p-link; /依次将链中结点进栈 p=L; /p 起到单链表尾指针作用 while (!isEmpty(S) /将栈中保存的结点依次出栈 pop (S,q);p-link=q; /出栈元
22、素链入逆置后的链中 p=p-link; /p 进到链表尾结点 p-link=NULL; /逆置后的链表收尾 22.编写一个算法，将一个非负的十进制整数 N 转换为一个二进制数。 （分数：4.00）_正确答案：()解析：可以利用栈解决数制转换问题，将一个非负的十进制整数转换为一个二进制数。例如：49 10 =12 5 +12 4 +12 0 =110001 2 ， 99 10 =12 6 +12 5 +02 4 +02 3 +02 2 +12 1 +12 0 =1100011 2 。 其转换规则是： 其中，b i 表示二进制数的第 i 位上的数字。这样，十进制数 N 可以用长度为 +1 位的二进
23、制数表示为 。若令 23.试编写一个算法，检查一个程序中的花括号、方括号和圆括号是否配对，若能够全部配对则返回 1，否则返回 0。 （分数：4.00）_正确答案：()解析：在算法中，扫描程序中的每一个字符，当扫描到花、中、圆左括号时，令其进栈，当扫描到花、中、圆右括号时，则检查栈顶是否为相应的左括号，若是则作退栈处理，若不是则表明出现了语法错误，应返回 0。当扫描到程序文件结尾后，若栈为空则表明没有发现括号配对错误，应返回 1，否则表明栈中还有未配对的括号，应返回 0。另外，对于一对单引号或双引号内的字符不进行括号配对检查。 根据分析，编写出算法如下： int BracketsCheck (c
24、har * f) /对由 f 所指字符串中的文本进行括号配对检查 stack S;char ch; /定义一个栈 char * p=f; while(*p!=“0“) /顺序扫描字符串中的每一个字符 if ( * p=39) /单引号内的字符不参与配对比较 while ( * p!=“0“ else if( * p!=“0“ if ( * p!=“0“) switch ( * p) case“:case“:case“(“:push(S, * p);break; /左括号进栈 case“:getTop(S,ch); if(ch=“)pop(S,ch); /栈顶的左花括号出栈 else retur
25、n(0);break; case“:getTop(S,ch); if(ch=“)pop(S,ch); /栈顶的左中括号出栈 else return(0);break; case“)“:getTop (S,ch); if (ch=“(“)pop (S,ch); /栈顶的左圆括号出栈 else return(0); p+; if (isEmpty(S) return (1); else return (0); 24.将表达式的中缀表示转换为相应的后缀表示时，需要利用栈暂存某些操作符，现有一个表达式的中缀表示： a+b*(c-d)+e/f# 请给出转换为后缀表示时的处理过程及栈的相应变化。 提示：运
26、算符的优先级如下表所示，其中，icp 表示当前扫描到的运算符 ch 的优先级，该运算符进栈后的优先级为 isp，字符“#”为表达式结束符。 运算符 # ( *，/ +，- ) isp 0 1 5 3 6 icp 0 6 4 2 1 （分数：4.00）_正确答案：()解析：表达式的中缀表示：a+b*(c-d)+e/f#转换为相应的后缀表示时，需要利用栈暂存某些操作符。如下表所示。 步序 扫描项 项类型 动作 栈的变化 输出 0 “#“进 # 栈，读下一符号 1 a 操作数 直接输出，读下一符号 # a 2 + 操作数 isp(“#“)icp(“+“)，进栈，读下一符号 #+ 3 b 操作数 直接
27、输出，读下一符号 #+ b 4 * 操作数 isp(“+“)icp(“*“#+* )，进栈，读下一符号 5 ( 操作数 isp(“+“)icp(“(“)，进栈，读下一符号 #+*( 6 c 操作数 直接输出，读下一符号 #+*( c 7 - 操作数 isp(“(“)icp(“-“)，进栈，读下一符#+*(- 号 8 d 操作数 直接输出，读下一符号 #+*(- d 9 ) 操作数 isp(“-“)icp(“)“)，退栈输出 #+*( - 10 Isp(“(“)=icp(“)“)，退栈，读下一符号 #+* 11 + 操作数 isp(“*“)icp(“+“)，退栈输#+ * 出 12 isp(“+“)icp(“+“)，退栈输出 #+ + 13 isp(“#“)icp(“+“)，进栈，读下一符号 #+ 14 e 操作数 直接输出，读下一符号 #+ e 15 / 操作数 isp(“+“)icp(“/“)，进栈，#+/ 读下一符号 16 f 操作数 直接输出，读下一符号 #+/ f 17 # 操作数 isp(“/“)icp(“*“)，退栈输出 #+ / 18 isp(“+“)icp(“#“)，退栈输出 # + 19 isp(“#“)=icp(“#“)，退栈，结束
