数据结构形考测试二
一、单项选择题（每小题2分，共50分）
1. 若让元素1，2，3依次进栈，则出栈顺序不可能为（ C ）。
A. 3，2，1
B. 2，1，3
C. 3，1，2
D. 1，3，2
2. 一个队列的入队序列是1，2，3，4。则队列的输出序列是（ B ）。
A. 4，3，2，1
B. 1，2，3，4
C. 1，4，3，2
D. 3，2，4，1
3. 向顺序栈中压入新元素时，应当（ A ）。
A. 先移动栈顶指针，再存入元素
B. 先存入元素，再移动栈顶指针
C. 先后次序无关紧要
D. 同时进行
4. 在一个栈顶指针为top的链栈中，将一个p指针所指的结点入栈，应执行（ C ）。
A. top->next=p;
B. p->next=top->next;top->next=p;
C. p->next=top;top=p;
D. p->next=top->next;top=top->next;
5. 在一个栈顶指针为top的链栈中删除一个结点时，用 x保存被删结点的值，则执行（ D ）。
A. x=top;top=top->next;
B. x=top->data;
C. top=top->next;x=top->data;
D. x=top->data;top=top->next;
6. 判断一个顺序队列（最多元素为m）为空的条件是（ B ）。
A. rear==m-1
B. front==rear
C. rear=m
D. front==rear+1
7. 判断一个循环队列为满的条件是（ C ）。
A. rear=MaxSize
B. front==rear+1
C. (rear+1)%MaxSize==front
D. rear%MaxSize= =front
8. 判断栈满（元素个数最多n个）的条件是（ C ）。
A. top==0
B. top!=0
C. top==n-1
D. top=-1
9. 设有一个20阶的对称矩阵A（第一个元素为a1,1），采用压缩存储的方式，将其下三角部分以行序为主序存储到一维数组B中（数组下标从1开始）， 则矩阵元素a6,2在一维数组B中的下标是（ B ）。
A. 21
B. 17
C. 28
D. 23
10. 在解决计算机主机与打印机之间速度不匹配问题时通常设置一个打印数据缓冲区，主机将要输出的数据依次写入缓冲区中，而打印机则从缓冲区中取出数据打印，该缓冲区应该是一个（ B ）结构。
A. 堆栈
B. 队列
C. 数组
D. 线性表
11. 一个递归算法必须包括（ B ）。
A. 递归部分
B. 终止条件和递归部分
C. 迭代部分
D. 终止条件和迭代部分
12. 在一个链队中，假设f和r分别为队头和队尾指针，则删除一个结点的运算为（ C ）。
A. r=f->next;
B. r=r->next;
C. f=f->next;
D. f=r->next;
13. 在一个链队中，假设f和r分别为队头和队尾指针，则插入s所指结点的运算为（ B ）。
A. f->next=s;f=s;
B. r->next=s;r=s;
C. s->next=r;r=s;
D. s->next=f;f=s;
14. 数组a经初始化char a[ ]=“English”;a[7]中存放的是（ A ）。
A. 字符串的结束符
B. 字符h
C. "h"
D. 变量h
15. 设主串为“ABcCDABcdEFaBc”，以下模式串能与主串成功匹配的是（ A ）。
A. Bcd
B. BCd
C. ABC
D. Abc
16. 字符串 a1="AEIJING"，a2="AEI"，a3="AEFANG"，a4="AEFI"中最大的是（ A ）。
A. a1
B. a2
C. a3
D. a4
17. 两个字符串相等的条件是（ D ）。
A. 两串的长度相等
B. 两串包含的字符相同
C. 两串的长度相等，并且两串包含的字符相同
D. 两串的长度相等，并且对应位置上的字符相同
18. 一维数组A采用顺序存储结构，每个元素占用6个字节，第6个元素的存储地址为100，则该数组的首地址是（ C ）。
A. 64
B. 28
C. 70
D. 90
19. 一个非空广义表的表头（ D ）。
A. 不可能是原子
B. 只能是子表
C. 只能是原子
D. 可以是子表或原子
20. 对稀疏矩阵进行压缩存储,可采用三元组表，一个10 行8列的稀疏矩阵A，其相应的三元组表共有6个元素，矩阵A共有（ C ）个零元素。
A. 8
B. 72
C. 74
D. 10
21. 对稀疏矩阵进行压缩存储,可采用三元组表，一个10 行8列的稀疏矩阵A共有73个零元素，A的右下角元素为6，其相应的三元组表中的第7个元素是（ A ）。
A. （10，8，6）
B. （10，8，7）
C. （7，10，8）
D. （7，8，10）
22. 对一个栈顶指针为top的链栈进行入栈操作，通过指针变量p生成入栈结点，并给该 结点赋值a，则执行: p=(struct node *)malloc(sizeof(struct node);p->data=a;和（ A ）。
A. p->next=top;top=p;
B. top->next=p;p=top;
C. top=top->next;p=top;
D. p->next=top;p=top;
23. 头指针为head的带头结点的单向链表为空的判定条件是（ C ）为真。
A. head==NULL
B. head->next!=NULL
C. head->next==NULL
D. head->next!=NULL
24. 设有一个对称矩阵A，采用压缩存储的方式，将其下三角部分以行序为主序存储到一维数组B中（数组下标从1开始），B数组共有55个元素,则该矩阵是（ C ）阶的对称矩阵。
A. 5
B. 20
C. 10
D. 15
25. 数组a经初始化char a[ ]=“English”;a[1]中存放的是（ A ）。
A. 字符n
B. 字符E
C. "n"
D. "E"
二、判断题（每小题2分，16题，共32分 ）
26. 设有一个链栈，栈顶指针为hs，现有一个s所指向的结点要入栈，则可执行操作。hs=s；
s-> next=hs;（B）
A. 对
B. 错
27. 设有一个非空的链栈，栈顶指针为hs，要进行出栈操作，用x保存出栈结点的值，栈
结点的指针域为next，则可执行hs=hs->next ;x=hs->data; （B）
A. 对
B. 错
28. 有一个链栈，栈顶指针为h，现有一个p所指向的结点要入栈，则可执行操作p->next=h;
和h=p；（A）
A. 对
B. 错
29. 设有一个非空的链栈，栈顶指针为hs，要进行出栈操作，用x保存出栈结点的值，栈结点的指针域为next，数据域为data，则可执行hs= hs->next; x= hs->data; （B）
A. 对
B. 错
30. 在一个链队中，f和r分别为队头和队尾指针，队结点的指针域为next，则插入所指结点的操作为r->next=s；r=s；（A）
A. 对
B. 错
31. 在一个链队中，f和r分别为队头和队尾指针，队结点的指针域为next，s指向一个要入 队的结点，则入队操作为r=s；r->next=s；（B）
A. 对
B. 错
32. 在一个不带头结点的非空链队中，f和r分别为队头和队尾指针，队结点的数据域为data，指针域为next，若要进行出队操作，并用变量x存放出队元素的数据值，则相关操作为x=f->data; f=f->next; （A）
A. 对
B. 错
33. 对稀疏矩阵进行压缩存储,可采用三元组表，一个6行7列的稀疏矩阵A相应的三元组表共有8个元素,则矩阵A共有34个零元素。（A）
A. 对
B. 错
34. 循环队列的最大存储空间为MaxSize，队头指针为f，队尾指针为r，当（r+1）%MaxSize=f 时表明队列已满。（A）
A. 对
B. 错
35. 循环队列的队头指针为f，队尾指针为r，当r= =f时表明队列已满。（B）
A. 对
B. 错
36. 空串的长度是0；空格串的长度是空格字符的个数。（A）
A. 对
B. 错
37. 对稀疏矩阵进行压缩存储，矩阵中每个非零元素对应的三元组包括该元素的行下标、列下标、和非零元素值三项信息。（A）
A. 对
B. 错
38. 循环队列的引入，目的是为了克服假上溢。（A）
A. 对
B. 错
39. 设有n阶对称矩阵A，用一维数组s压缩存储A的下三角元素，s的下标从零开始，元素 s[26]相应于A中的元素为a7,5。（B）
A. 对
B. 错
40. 循环队列的最大存储空间为MaxSize=6，采用少用一个元素空间以有效的判断栈空或栈满，若队头指针front=4，当队尾指针rear=3时队满。（A）
A. 对
B. 错
41. 循环队列的最大存储空间为MaxSize=6，采用少用一个元素空间以有效的判断栈空或栈满，若队头指针front=4，队尾指针rear=3时，队列中共有5个元素。（A）
A. 对
B. 错
三、程序选择填空题（每小题9分，共18分。）
42. 以下函数为链栈的进栈操作，x是要进栈的结点的数据域，top为栈顶指针
struct node
{ ElemType data;
struct node *next;
};
struct node *top ;
void Push(ElemType x)
{
struct node *p;
p=(struct node*)malloc __(1)__;
p->data=x;
__(2)__;
__(3)__;
}
答案：
（1）sizeof (struct node)
（2）p->next=top
（3）top=p
43. 以下函数为链队列的入队操作，x为要入队的结点的数据域的值，front、rear分别链队列的队头、队尾指针
struct node
{ ElemType data;
struct node *next;
};
struct node *front，*rear;
void InQueue(ElemType x)
{
struct node *p;
p= (struct node*) malloc __(1)__;
p->data=x;
p->next=NULL;
__(2)__;
rear= __(3)__;
}
答案：
（1）(sizeof (struct node)
（2）rear->next=p
（3）p
