专升本数据结构试题解析(12)
时间:2025-07-10
时间:2025-07-10
数据结构上机实验与习题解析 亱店↘打烊oO
A)1和 5 B)2和4 C)4和2 D)5和1
【答案】B
【解析】循环队列是解决假溢出的问题,通常把一维数组看成首尾相接。在循环意义下的加1运算通常用求模运算来实现。所以入队和出队时的操作分别为:rear=(rear+1)%m,front=(front+1)%m。
10.栈和队列的共同点是( )
A)都是先进先出 B)都是先进后出
C)只允许在端点处插入和删除元素 D)没有共同点
【答案】C
【解析】栈和队列都是运算受限的线性表,只允许在表端点处进行操作。
11.在一个链队列中,假定front和rear分别为队头和队尾指针,则插入*s结点的操作为( )
A)front->next=s;front=s; B)s->next=rear;rear=s;
C)rear->next=s;rear=s; D)s->next=front;front=s;
【答案】C
【解析】队列是运算受限的线性表(FIFO),插入元素只能插在队尾,所以需修改队尾指针。
12.判定一个栈S(元素个数最多为MAXSIZE)为空和满的条件分别为( )
A)S->top!=-1 S->top!=MAXSIZE-1
B)S->top=-1 S->top=MAXSIZE-1
C)S->top=-1 S->top!=MAXSIZE-1
D)S->top!=-1 S->top=MAXSIZE-1
【答案】B
13.循环顺序队列中是否可以插入下一个元素( )
A)与队头指针和队尾指针的值有关
B)只与队尾指针的值有关,与队头指针的值无关
C)只与数组大小有关,而与队头指针和队尾指针的值无关
D)与曾经进行过多少次插入操作有关
【答案】A
【解析】在循环队列中判断队满的条件为:(q.rear+1)%m==q.front是否为真,从中可以看出,与队头指针和队尾指针的值有关。
14.最不适合用作链队的链表是( )
A)只带队头指针的非循环双链表 B)只带队头指针的循环双链表
C)只带队尾指针的非循环双链表 D)只带队尾指针的循环单链表
【答案】A
【解析】链队是在链表的两端进行操作,而在A中查找链表最后一个结点的时间复杂度为O(n)。
15.下列哪中数据结构常用于系统程序的作业调度( )
A)栈 B)队列 C)链表 D)数组
【答案】B
【解析】作业调度采用先到先服务的方式,因此最适合的数据结构为队列。
3.2 填空题
1.栈是_____________的线性表,其运算遵循_____________的原则。
【答案】(1)操作受限(或限定仅在表尾进行插入和删除操作) (2)后进先出
2.设有一个空栈,栈顶指针为1000H(十六进制),现有输入序列为1,2,3,4,5,经过PUSH,PUSH,POP,PUSH,POP,PUSH,PUSH之后,输出序列是_____________,而栈顶指针值是_____________H。设栈为顺序栈,每个元素占4个字节。
【答案】(1)23 (2)100CH
【解析】PUSH为入栈操作,POP为出栈操作。根据栈的性质,经过PUSH,PUSH,POP运算之后,栈中存在元素1,输出数据为2,然后经过PUSH,POP,3入栈,3出栈,然后经过PUSH,PUSH之后4,5入栈,此时出栈序列为2,3,栈中元素为1,4,5;每个元素占4个字节,所以栈顶指针的值为1000H+3*4=100CH(十六进制数)
3.循环队列的引入,目的是为了克服_____________。
【答案】假溢出时大量移动数据元素。
4.队列是限制插入只能在表的一端,而删除在表的另一端进行的线性表,其特点是_____________。