第 1 页 共 2 1 页 《数据结构》题库及答案 一、选择题 1．线性表的顺序存储结构是一种 的存储结构，线性表的链式存储结构是一种 的存储结构。 a. 随机存储； b.顺序存储； c. 索引存取； d. HASH 存取 2．一个栈的入栈序列是 a,b,c,d,e，则栈的不可能的输出序列是 。 a. edcba; b. decba; c. dceab; d.abcde 3．一个队列的入队序列是 1，2，3，4，则队列的输出序列是 。 a. 4,3,2,1; b. 1,2,3,4; c. 1,4,3,2; d.3,2,4,1 4．在一个单链表中，已知 p 结点是 q 结点的直接前驱结点，若在 p 和 q 之间插入结点 s，则执行的操作是 。 a. s->nxet=p->next; p->next=s; b. p->next=s->next; s->next=p; c. q->next=s; s->next=p; d. p->next=s; s->next=q; 5．设有两个串 p,q，求 q 在 p 中首次出现的位置的运算称作 。 a.联接 b.模式匹配 c.求子串 d.求串长 6．二维数组 M 的成员是 6 个字符（每个字符占一个存储单元）组成的串，行下标 i 的范围从 0 到 8，列下标 j的范围从 1 到 10，则存放 M 至少需要 个字节。 a. 90 b.180 c.240 d.540 7．在线索二叉树中，结点 p 没有左子树的充要条件是 。 a. p->lch==NULL b. p->ltag==1 c. p->ltag==1 且 p->lch=NULL d. 以上都不对 8．在栈操作中，输入序列为（A，B，C，D），不可能得到的输出序列为：______ A、（A，B，C，D） B、（D，C，B，A） C、（A，C，D，B） D、（C，A，B，D） 9．已知某二叉树的后序序列是 dabec，中序序列是 debac，则它的先序序列是 。 A、acbed B、decab C、deabc D、cedba 10．设矩阵 A 是一个对称矩阵，为了节省存储空间，将其下三角部分（见下图）按行序存放在一维数组B[1..n(n-1)/2]中，对任一上三角部分元素)(jiaij，在一维数组 B 的存放位置是 。 第 2 页 共 21 页 n nnnaaaaaaA21222111 A、12)1(jii B、12)1(ijj C、ijj2)1( D、jii2)1( 11． 图G 中有n 个顶点，n-1 条边，那么图G 一定是一棵树吗？ 。 A、 一定是 B、一定不是 C、不一定 12． 用某种排序方法对关键字序列{25，84，21，47，15，27，68，35，20}进行排序时，元素序列的变化情况如下： ① {25，84，21，47，15，27，68，35，20} ② {20，15，21，25，47，27，68，35，84} ③ {15，20，21，25，35，27，47，68...
