考研专业课之统考计算机蓝宝书(16)

2.5 习题练习

1 一个栈的输入序列为123...n，若输出序列的第一个元素是n，输出第i（1<=i<=n）个元素是（）。
A. 不确定 B. n-i+1 C. i D. n-i

2 有六个元素6，5，4，3，2，1 的顺序进栈，问下列哪一个不是合法的出栈序列？（）
A. 5 4 3 6 1 2 B. 4 5 3 1 2 6 C. 3 4 6 5 2 1 D. 2 3 4 1 5 6

3 输入序列为ABC，可以变为CBA时，经过的栈操作为（）
A. push,pop,push,pop,push,pop B. push,push,push,pop,pop,pop
C. push,push,pop,pop,push,pop D. push,pop,push,push,pop,pop

4 若栈采用顺序存储方式存储，现两栈共享空间V[1..m]，top[i]代表第i个栈( i =1,2)栈顶，栈1的底在v[1]，栈2的底在V[m]，则栈满的条件是（）。
A. |top[2]-top[1]|=0 B. top[1]+1=top[2] C. top[1]+top[2]=m D. top[1]=top[2]

5 栈在（）中应用。
A. 递归调用 B. 子程序调用 C. 表达式求值 D. A，B，C

6 执行完下列语句段后，i值为：（）
int f(int x)
{ return ((x>0) ? x* f(x-1):2);}
int i ;
i =f(f(1));
A．2 B. 4 C. 8 D. 无限递归

订阅收藏考研专业课之统考计算机蓝宝书

11 栈和队列的共同点是（）。
A. 都是先进先出 B. 都是先进后出
C. 只允许在端点处插入和删除元素 D. 没有共同点

12 设栈S和队列Q的初始状态为空，元素e1，e2，e3，e4,e5和e6依次通过栈S，一个元素出栈后即进队列Q，若6个元素出队的序列是e2，e4，e3,e6,e5,e1则栈S的容量至少应该是( )。
A． 6 B. 4 C. 3 D. 2

13 消除递归不一定需要使用栈，这种说法（）
A．正确 B. 错误 C. 不一定

14 设有一个10阶的对称矩阵A，采用压缩存储方式，以行序为主存储，a11为第一元素，其存储地址为1，每个元素占一个地址空间，则a85的地址为（）。
A. 13 B. 33 C. 18 D. 40

15 假设以行序为主序存储二维数组A=array[1..100，1..100]，设每个数据元素占2个存储单元，基地址为10，则LOC[5，5]=（）。
A. 808 B. 818 C. 1010 D. 1020

16 若对n阶对称矩阵A以行序为主序方式将其下三角形的元素(包括主对角线上所有元素)依次存放于一维数组B［1..(n(n+1))/2］中，则在B中确定aij（iA. i*(i-1)/2+j B. j*(j-1)/2+i C. i*(i+1)/2+j D. j*(j+1)/2+i
17 数组A[0..4,-1..-3,5..7]中含有元素的个数（）。
A. 55 B. 45 C. 36 D. 16

18 什么是递归程序？递归程序的优、缺点是什么？递归程序在执行时，应借助于什么来完成？递归程序的入口语句、出口语句一般用什么语句实现？

问：(1) 若x为局部变量时；该函数递归结束后返回调用程序的sum=? 并画出在递归过程中栈状态的变化过程；
(2) 若x为全程变量递归结束时返回调用程序的sum=?

21 若以1、2、3、4作为双端队列的输入序列，试分别求出以下条件的输出序列：
（1）能由输入受限的双端队列得到，但不能由输出受限的双端队列得到的输出序列；
（2）能由输出受限的双端队列得到，但不能由输入受限的双端队列得到的输出序列；
（3）既不能由输入受限的双端队列得到，也不能由输出受限的双端队列得到的输出序列

22 设有两个栈S1,S2都采用顺序栈方式，并且共享一个存储区[O..maxsize-1],为了尽量利用空间，减少溢出的可能，可采用栈顶相向，迎面增长的存储方式。试设计S1,S2有关入栈和出栈的操作算法。

23 请利用两个栈S1和S2来模拟一个队列。已知栈的三个运算定义如下：PUSH(ST,x):元素x入ST栈；POP(ST,x)：ST栈顶元素出栈，赋给变量x；Sempty(ST)：判ST栈是否为空。那么如何利用栈的运算来实现该队列的三个运算：enqueue:插入一个元素入队列； dequeue:删除一个元素出队列；queue_empty：判队列为空。（请写明算法的思想及必要的注释）

24 假设按低下标优先存储整型数组A（-3:8,3:5,-4:0,0:7）时，第一个元素的字节
存储地址是100，每个整数占4个字节，问A（0，4，-2，5）的存储地址是什么？

25 特殊矩阵和稀疏矩阵哪一种压缩存储后失去随机存取的功能？为什么？

26 设有上三角矩阵(aij)n*n，将其上三角中的元素按先行后列的顺序存于数组B（1:m）中，使得B[k]= aij且k=f1(i)+f2(j)+c，请推导出函数f1,f2和常数c，要求f1和f2中不含常数项。

考研专业课之统考计算机蓝宝书(16)

猜你喜欢

阅读排行榜