发布时间 : 星期一 文章数据结构更新完毕开始阅读
随后输入英语单词个数，试编写算法建立一个单链表，要求：如果单词重复出现，则只在链表上只保留一个；统计单词出现的次数，然后输出次数最多的前k(k 典型题目解析 静态链表 1、静态链表中的指针是（） A、下一元素的地址 B、内存储器的地址 C、下一元素在数组中的位置 D、左链或者右链指向的元素的地址 2、静态链表的相关说法错误的是 ①静态链表既有顺序表的优点又有动态链表的优点，所以，它存取表中第i个元素的时间与i无关。 ②静态链表中能容纳的元素个数在定义表时必须是确定的。 ③静态链表与动态链表在元素的插入、删除上类似，不需要做元素的移动。 A ① ② B ① C ① ② ③ D ② 第三章 栈和队列 考纲分析 二、栈、队列和数组 （一）栈和队列的基本概念 （二）栈和队列的顺序存储结构（三）栈和队列的链式存储结构（四）栈和队列的应用 （五）特殊矩阵的压缩存储 典型题目解析 栈 1、若一个栈的输入序列是1，2，3，?，n，输出序列是p1，p2，p3?若p1=3，则p2的值是( ) A、一定是2 B、一定是1 C、不可能是1 D、都不对 2、若一个栈的输入序列是p1，p2，?pn，其输出序列是1，2，3?若p3=1，则p1的值是( ) A、可能是2 B、一定是2 C、不可能是2 D、不可能是3 3、表达式3*2^(4+2*2-6*3)-5求值过程中，当扫描到6时，对象栈和算符栈为（ ）。 4、利用栈计算表达式的值时，设置操作数栈OPND，设OPND只有两个存储单元，计算下列表达式时不发生上溢的是（ ） A、a-b*(c-d) B、(a-b)*c-d C、(a-b*c)-d D、(a-b)*(c-d) 5、在表达式求值的运算符栈中，从栈顶到栈底的运算符的优先级是（ ） A、从高到低 B、从低到高 C、无序 D、可能有序可能无序 6、与中缀表达式a*b+c/d-e等价的后缀表达式是（ ） 7、向一个栈顶指针为h的带头结点的链栈中插入指针s所指的结点时，执行（ ） A、h->next=s; B、s->next=h; C、s->next=h;h->next=s D、s->next=h->next;h->next=s; 8、设数组S[n]作为两个栈S1和S2的存储空间，对任何一个栈只有当S[n]全满时才不能进行进栈操作。为这两个栈分配空间的最佳方案是（ ） 9 A、S1的栈底位置为0，S2的占地位置为n-1 B、S1的栈底位置为0，S2的占地位置为n/2 C、S1的栈底位置为0，S2的占地位置为n D、S1的栈底位置为0，S2的占地位置为1 9、如上题，这样分配的好处是（ ） 10、下列最有效表示栈的链表结构是（ ） A、带头结点的单链表 B、单链表 C、带头结点的双向链表D、双向链表 11、消除递归不一定使用栈，此说法（ ） 12、任何一个递归过程都可以转换成非递归过程。（ ） 13、只有那种使用了局部变量的递归过程在转换成非递归过程时才必须使用栈（ ） 14、用单链表表示栈，栈顶设在链表的（ ） 15、有5个元素，其入栈次序为A、B、C、D、E，在各种可能的出栈序列中，第一个出栈元素为C且第二个出战元素为D的出栈序列有哪几个？ 16、元素abcdef依次进栈，允许进栈、出栈交替进行，但不允许连续三次进行出栈操作，则不可能得到的出栈序列是（ ） A、dcebfa B、cbdaef C、bcaefd D、afedcb 17、元素abcde依次进栈，允许进栈、出栈交替进行，则以d为首的出栈序列是（ ） 18、设计一个算法，判断一个算术表达式中的括号是否匹配。算术表达式保存在带头结点的单循环链表中，每个结点有两个域：ch和link，其中ch域为字符类型。 典型题目解析 队列 1、若用一个长度为6的数组来实现循环队列，且当前rear和front的值分别为0和3，则队列中删除一个元素，再添加2个元素后，rear和front的值分别为（ ）。 2、循环队列的存储空间为数组A[21]，front指向队首元素的前一位置，rear指向队尾元素。假设当前front和rear的值分别是8和3，则队列的长度是（ ）。 3、最不适合用作链队列的链表是（ ） A 只带队首指针的非循环双链表 B 只带队首指针的循环双链表 C 只带队尾指针的循环双链表 D 只带队尾指针的循环单链表 4、下列更适合表示队列的链表结构是（ ） A、单链表B、单循环链表C、双链表D、双循环链表 5、执行（ ）操作时，需要队列作为辅助的存储结构 A、深度优先遍历图 B、广度优先遍历图 C、散列查找 D、遍历二叉树 10 6、用不带头结点的单链表存储队列，其对头指针指向队头结点，队尾指针指向队尾结点，则在进行出队操作时（ ） A、仅修改队头指针 B、仅修改队尾指针 C、队头队尾可能都要修改 D、C去掉可能 7、在带头结点的链队列中，队头指针应该指向（ ） 7、已知输入序列为abcd，经过输出受限的双向队列后能得到的输出序列有（ ） A dacb B cadb C dbca D bdac E all wrong 8、若以1234作为双端队列的输入序列，则既不能由输入受限的双端队列得到，也不能由输出受限的双段队列得到的是（ ） A、1234 B、4132 C、4231 D、4213 9、设栈S和队列Q的初始状态为空，元素e1，e2，e3，e4，e5和e6依次通过栈S，一个元素出栈后入队Q，若出队序列为e2,e4,e3,e6,e5,e1，则栈S的容量至少应该是（ ） 10、队列的队首和队尾分别指向最早进队，最后进队的元素，为使第一个进队元素在A[0]，front和rear分别指向? A、0,0； B、0,n-1； C、n-1,0; D、n-1,n-1; 11、某队列允许在其两端进行入队操作，但仅允许在一段进行出队操作。若元素abcde依次入队后再进行出队操作，则不可能得到的出队序列是( ) A、bacde B、dbace C、dbcae D、ecbad 12、关于队列的叙述中，正确的是（） A、只能使用数组构成循环队列 B、可以使用数组或者链表构成循环队列 C、循环队列没有元素数量限制 D、可以将栈看成是一个特殊的队列 13、若以1、2、3、4作为双端队列的输入序列，试分别求以下条件的输出序列： 能由输入受限的双端得到，但不能由输出受限的双端队列得到的输出序列； 能由输出受限的双端得到，但不能由输入受限的双端队列得到的输出序列； 既不能由输入受限的双端得到，也不能由输出受限的双端队列得到的输出序列； 14、利用两个栈S1、S2模拟一个队列时，如何利用栈的操作实现入队、出队及判断队列是否为空。 15、试用一个不带头结点的循环链表表示队列，说明链表指针指向何处？如何入队、出队及判断队列为空？ 16、设栈S中有2n个元素，从栈顶到栈底的元素依次为a2n,a2n-1,?,a1，要求通过一个循环队列重新排序站中元素，使得从栈顶到栈底的元素依次为a2n,a2n-2, ?,a2,a2n-1,a2n-3, ?,a1，设计算法实现，要求空间复杂度和时间复杂度为O(n)。 11 典型题目解析 数组 1、二维数组S[-3..5,0..10]含有的元素个数是（ ）。 2、二维数组A的每个元素由6个字符组成，行下标的范围是0~8，列下标的范围是从0~9，则存放A需要（ ）字节；A的第8列和第5行共占（ ）字节；若A按行优先方式存储，元素A[8][5]的起始地址与当A按列优先方式存储时的（ ）元素的起始地址一致。 3、四维数组A[8,9,10,11]采用行序为主序的方式从地址A[0,0,0,0]开始存放，假设每个元素占用存储空间大小为L，则元素A[3,4,8,10]的存放地址是（ ）。 典型题目解析 矩阵的压缩存储 特殊矩阵是指矩阵中有较多相同的元素且其分布有一定的规律；压缩存储的基本思想是：为多个相同的元素分配一个存储空降；对零元素不分配存储空间。 1、设A[N,N]是对称矩阵，将其下三角包括对角线按行序存储到一维数组T[N(N+1)/2]中，则上三角元素A[i][j]对应数组元素T的下标是（ ） 2、对特殊矩阵采用压缩存储的目的主要是（ ） A、表达变的简单 B、对矩阵元素的存取变得简单 C、去掉矩阵中的多余元素 D、减少不必要的存储空间 3、设有一个n行n列的对称矩阵A，将其下三角部分按行存放在一维数组B中，A[0][0]存放于B[0]中，则第i行的对角元素A[i][i]存放于B中（ ）处。 4、若将n阶下三角矩阵A按列优先顺序压缩存放在一维数组B[1..n(n+1)/2]中，则存放到B[k]中的非零元素aij的下标i,j与k的对应关系是（ ）。 5、将一个A[1..100,1..100]的三对角矩阵，按行优先存入一维数组B[1..298]中，则A中元素A[66,65]在B数组中的位置K为（ ）。 第五章 树和二叉树 考纲分析 （一）树的基本概念 （二）二叉树 1.二叉树的定义及其主要特征 2.二叉树的顺序存储结构和链式存储结构 3.二叉树的遍历 4.线索二叉树的基本概念和构造 （三）树、森林 1.树的存储结构 2.森林与二叉树的转换 3.树和森林的遍历 （四）树与二叉树的应用 1.二叉排序树 2.平衡二叉树 3.哈夫曼（Huffman）树和哈夫曼编码 典型题目解析 树的基本概念 1、假定一颗度为3的树中结点数为50，则其最小高度应为（ ）。 2、下列说法中，（ ）是正确的。 A、二叉树就是度为2的树 B、二叉树中不存在度大于2的结点 C、二叉树是有序树 D、二叉树中每个结点的度均为2 3、二叉树是一棵（ ） A、度为2的有序树 B、所有结点度均为2的有序树 C、度为2的无序树 D、所有结点度均为2的无序树 4、下列情况中，可称为二叉树的是（ ） A、每个结点至多有两棵子树的树 B、哈夫曼树 12