数据结构形考作业2

1、一、单项选择题（每小题2分，共50分）题目1若让元素1，2，3依次进栈，则出栈顺序不可能为（ ）。选择一项：A. 3，2，1B. 2，1，3C. 1，3，2D. 3，1，2题目2一个队列的入队序列是1，2，3，4。则队列的输出序列是（ ）。选择一项：A. 4，3，2，1B. 1，2，3，4C. 1，4，3，2D. 3，2，4，1题目3向顺序栈中压入新元素时，应当（ ）。选择一项：A. 先移动栈顶指针，再存入元素B. 同时进行C. 先后次序无关紧要D. 先存入元素，再移动栈顶指针题目4在一个栈顶指针为top的链栈中，将一个p指针所指的结点入栈，应执行（ ）。选择一项：A. top-next=p;

2、B. p-next=top-next;top-next=p;C. p-next=top-next;top=top-next;D. p-next=top;top=p;题目5在一个栈顶指针为top的链栈中删除一个结点时，用 x保存被删结点的值，则执行（ ）。选择一项：A. top=top-next;x=top-data;B. x=top-data;C. x=top;top=top-next;D. x=top-data;top=top-next;题目6判断一个顺序队列（最多元素为m）为空的条件是（ ）。选择一项：A. rear=m-1B. front=rearC. front=rear+1D. re

3、ar=m题目7判断一个循环队列Q（最多元素为m）为满的条件是（ ）。选择一项：A. Q-front=Q-rearB. Q-front=Q-rear +1C. Q-rear!= (Q-front+1)%mD. Q-front=(Q-rear+1)%m题目8判断栈满（元素个数最多n个）的条件是（ ）。选择一项：A. top=0B. top=-1C. top=n-1D. top!=0题目9设有一个20阶的对称矩阵A（第一个元素为a1,1），采用压缩存储的方式，将其下三角部分以行序为主序存储到一维数组B中（数组下标从1开始）， 则矩阵元素a6,2在一维数组B中的下标是（ ）。选择一项：A. 23B.

4、17C. 21D. 28题目10在解决计算机主机与打印机之间速度不匹配问题时通常设置一个打印数据缓冲区，主机将要输出的数据依次写入缓冲区中，而打印机则从缓冲区中取出数据打印，该缓冲区应该是一个（ ）结构。选择一项：A. 队列B. 先性表C. 数组D. 堆栈题目11一个递归算法必须包括（ ）。选择一项：A. 递归部分B. 迭代部分C. 终止条件和递归部分D. 终止条件和迭代部分题目12在一个链队中，假设f和r分别为队头和队尾指针，则删除一个结点的运算为（ ）。选择一项：A. r=f-next;B. f=f-next;C. f=r-next;D. r=r-next;题目13在一个链队中，假设f和r

5、分别为队头和队尾指针，则插入s所指结点的运算为（ ）。选择一项：A. s-next=f;f=s;B. r-next=s;r=s;C. s-next=r;r=s;D. f-next=s;f=s;题目14数组a经初始化char a =“English”;a7中存放的是（ ）。选择一项：A. 字符hB. hC. 字符串的结束符D. 变量h题目15设主串为“ABcCDABcdEFaBc”，以下模式串能与主串成功匹配的是（ ）。选择一项：A. ABCB. AbcC. BcdD. BCd题目16字符串 a1=AEIJING，a2=AEI，a3=AEFANG，a4=AEFI中最大的是（ ）。选择一项：A.

6、a2B. a1C. a3D. a4题目17两个字符串相等的条件是（ ）。选择一项：A. 两串的长度相等，并且两串包含的字符相同B. 两串的长度相等C. 两串包含的字符相同D. 两串的长度相等，并且对应位置上的字符相同题目18一维数组A采用顺序存储结构，每个元素占用6个字节，第6个元素的存储地址为100，则该数组的首地址是（ ）。选择一项：A. 28B. 64C. 90D. 70题目19一个非空广义表的表头（ ）。选择一项：A. 可以是子表或原子B. 不可能是原子C. 只能是子表D. 只能是原子题目20对稀疏矩阵进行压缩存储,可采用三元组表，一个10 行8列的稀疏矩阵A，其相应的三元组表共有6个

7、元素，矩阵A共有（ ）个零元素。选择一项：A. 74B. 10C. 72D. 8题目21对稀疏矩阵进行压缩存储,可采用三元组表，一个10 行8列的稀疏矩阵A共有73个零元素，A的右下角元素为6，其相应的三元组表中的第7个元素是（ ）。选择一项：A. （7，8，10）B. （7，10，8）C. （10，8，7）D. （10，8，6）题目22对一个栈顶指针为top的链栈进行入栈操作，通过指针变量p生成入栈结点，并给该 结点赋值a，则执行: p=(struct node *)malloc(sizeof(struct node);p-data=a;和（ ）。选择一项：A. top-next=p;p=t

8、op;B. p-next=top;p=top;C. top=top-next;pe=top;D. p-nex=top;top=p;题目23头指针为head的带头结点的单向链表为空的判定条件是（ ）为真。选择一项：A. head-next=NULLB. head-next!=NULLC. head=NULLD. head-next!=NULL题目24设有一个对称矩阵A，采用压缩存储的方式，将其下三角部分以行序为主序存储到一维数组B中（数组下标从1开始），B数组共有55个元素,则该矩阵是（ ）阶的对称矩阵。选择一项：A. 20B. 15C. 5D. 10题目25数组a经初始化char a =“En

9、glish”;a1中存放的是（ ）。选择一项：A. nB. 字符nC. 字符ED. E二、填空题（每小题2分，共30分）题目26循环队列队头指针在队尾指针下一个位置，队列是“满”状态。题目27循环队列的引入，目的是为了克服假上溢。题目28判断一个循环队列LU（最多元素为m）为空的条件是LU-front=LU-rear。题目29向一个栈顶指针为h的链栈中插入一个s所指结点时，可执行s-next=h和h=s;操作。（结点的指针域为next）题目30从一个栈顶指针为h的链栈中删除一个结点时，用x保存被删结点的值，可执行x=h-data;和 h=h-next。（结点的指针域为next）题目31在一个链

10、队中，设f和r分别为队头和队尾指针，则插入s所指结点的操作为r-next=s和r=s;（结点的指针域为next）题目32在一个链队中，设f和r分别为队头和队尾指针，则删除一个结点的操作为f=f-next。 （结点的指针域为next）题目33串是一种特殊的线性表，其特殊性表现在组成串的数据元素都是字符。题目34空串的长度是0；空格串的长度是空格字符的长度。题目35设广义表L=(),()，则表头是_，表尾是_，L的长度是_。表头是（），表尾是（），L的长度是2题目36广义表A（a，b，c），（d，e，f）的表尾为d,e,f。题目37设有n阶对称矩阵A，用数组s进行压缩存储，当ij时，A的数组元素a

11、ij相应于数组s的数组元素的下标为i=(i-1)/2+j。（数组元素的下标从1开始）题目38对稀疏矩阵进行压缩存储，矩阵中每个非零元素对应的三元组包括该元素的_、_和_三项信息。行下标、列下标和非零元素值题目39循环队列用a0，a7的一维数组存放队列元素，（采用少用一个元素的模式)，设front和rear分别为队头和队尾指针，且front和rear 的值分别为2和7，当前队列中的元素个数是5。题目40循环队列的引入，目的是为了克服假上溢。三、问答题（每小题5分，共20分）题目41栈、队列和线性表的区别是什么？答：栈是一种先进后出的线性表，栈的插入和删除操作都只能在栈顶进行，而一般的线性表合一在

12、线性表的任何位置进行插入和删除操作。队列是一种先进先出的线性表，队列的插入只能在队尾进行，队列的删除只能在队头进行，而一般的线性表可以在线性表的任何位置进行插入和删除操作题目42设栈S和队列Q的初始状态为空，元素e1，e2，e3，e4，e5和e6依次通过S，一个元素出栈后即进队列Q，若6个元素出队的序列是e2，e4，e3，e6，e5，e1，则栈S的容量至少应该是多少？出队序列是e2,e4,e3,e6,e5,e1的过程：（1）e1入栈（栈底到栈顶元素是e1）（2）e2入栈（栈底到栈顶元素是e1,e2）（3）e2出栈（栈底到栈顶元素是e1）（4）e3入栈（栈底到栈顶元素是e1,e3）（5）e4入栈

13、（栈底到栈顶元素是e1,e3,e4）（6）e4出栈（栈底到栈顶元素是e1,e3）（7）e3出栈（栈底到栈顶元素是e1）（8）e5入栈（栈底到栈顶元素是e1,e5）（9）e6入栈（栈底到栈顶元素是e1,e5,e6）（10）e6出栈（栈底到栈顶元素是e1,e5）（11）e5出栈（栈底到栈顶元素是e1）（12）e1出栈（栈底到栈顶元素是空）栈中最多时有3个元素，所以栈S的容量至少是3题目43有5个元素，其入栈次序为：A、B、C、D、E，在各种可能的出栈次序中，以元素C、D最先的次序有哪几个？从题中可知，要使C第一个且D第二个出栈，应是A入栈，B入栈，C入栈，C出栈，D入栈，D出栈，之后可以有一下几种情况：（1）B出栈，E入栈，E出栈，A出栈，CDBEA（2）E入栈