1、第一部分1.栈和队列的共同特点是(只允许在端点处插入和删除元素)2.栈通常采用的两种存储结构是(线性存储结构和链表存储结构)3.链表不具有的特点是(B)A.不必事先估计存储空间 B.可随机访问任一元素C.插入删除不需要移动元素 D.所需空间与线性表长度成正比4.用链表表示线性表的优点是(便于插入和删除操作)5.在单链表中,增加头结点的目的是(方便运算的实现)6.循环链表的主要优点是(从表中任一结点出发都能访问到整个链表)7.线性表若采用链式存储结构时,要求内存中可用存储单元的地址(D)A.必须是连续的 B.部分地址必须是连续的C.一定是不连续的 D.连续不连续都可以8.线性表的顺序存储结构和线
2、性表的链式存储结构分别是(随机存取的存储结构、顺序存取的存储结构)9.具有 3个结点的二叉树有(5 种形态)10.设一棵二叉树中有 3个叶子结点,有 8个度为 1的结点,则该二叉树中总的结点数为(13)(n 0 = n2 +1)11.已知二叉树后序遍历序列是 dabec,中序遍历序列是 debac,它的前序遍历序列是(cedba)12.若某二叉树的前序遍历访问顺序是 abdgcefh,中序遍历访问顺序是dgbaechf,则其后序遍历的结点访问顺序是(gdbehfca)13.数据库保护分为:安全性控制、完整性控制、并发性控制和数据的恢复。第二部分1.在计算机中,算法是指(解题方案的准确而完整的描
3、述)2.算法一般都可以用哪几种控制结构组合而成(顺序、选择、循环)3.算法的时间复杂度是指(算法执行过程中所需要的基本运算次数)4.算法的空间复杂度是指(执行过程中所需要的存储空间)5.算法分析的目的是(分析算法的效率以求改进)6.下列叙述正确的是(C)A算法的执行效率与数据的存储结构无关B算法的空间复杂度是指算法程序中指令(或语句)的条数C算法的有穷性是指算法必须能在执行有限个步骤之后终止D算法的时间复杂度是指执行算法程序所需要的时间7.数据结构作为计算机的一门学科,主要研究数据的逻辑结构、对各种数据结构进行的运算,以及(数据的存储结构)8.数据结构中,与所使用的计算机无关的是数据的(C)A
4、存储结构 B物理结构 C逻辑结构 D物理和存储结构9.下列叙述中,错误的是(B)A数据的存储结构与数据处理的效率密切相关B数据的存储结构与数据处理的效率无关C数据的存储结构在计算机中所占的空间不一定是连续的D一种数据的逻辑结构可以有多种存储结构10.数据的存储结构是指(数据的逻辑结构在计算机中的表示)11.数据的逻辑结构是指(反映数据元素之间逻辑关系的数据结构)12.根据数据结构中各数据元素之间前后件关系的复杂程度,一般将数据结构分为(线性结构和非线性结构)13.下列数据结构具有记忆功能的是(C)A队列 B循环队列 C栈 D顺序表14.递归算法一般需要利用(栈)实现。15.由两个栈共享一个存储
5、空间的好处是(节省存储空间,降低上溢发生的机率)16.与单向链表相比,双向链表的优点之一是(更容易访问相邻结点)17.设一棵完全二叉树共有 699个结点,则在该二叉树中的叶子结点数为(350)说明:完全二叉树总结点数为 N,若 N为奇数,则叶子结点数为(N+1)/2;若 N为偶数,则叶子结点数为 N/2。18.串的长度是(串中所含字符的个数)19.设有两个串 p和 q,求 q在 p中首次出现位置的运算称做(模式匹配)20.N个顶点的连通图中边的条数至少为(N-1)21.N个顶点的强连通图的边数至少有(N)22.对长度为 n的线性表进行顺序查找,在最坏情况下所需要的比较次数为(n)23.最简单的
6、交换排序方法是(冒泡排序)24.假设线性表的长度为 n,则在最坏情况下,冒泡排序需要的比较次数为(n(n-1)/2)25.在待排序的元素序列基本有序的前提下,效率最高的排序方法是(冒泡排序)26.希尔排序法属于(插入类排序)27.堆排序法属于(选择类排序)28.已知数据表 A中每个元素距其最终位置不远,为节省时间,应采用(直接插入排序)29.算法的基本特征是有穷性、可行性、确定性和拥有足够的情报。第三部分1.一个算法通常由两种基本要素组成:一是对数据对象的运算和操作,二是算法的控制结构。2.所谓数据处理是指对数据集合中的各元素以各种方式进行运算,包括插入、删除、查找、更改等运算,也包括对数据元
7、素进行分析。3.数据结构是指相互有关联的数据元素的集合。4.数据结构分为逻辑结构与存储结构,线性链表属于(存储结构)。5.数据元素之间的任何关系都可以用前驱和后继关系来描述。6.数据的逻辑结构有线性结构和非线性结构两大类。7.常用的存储结构有顺序、链接、索引等存储结构。8.栈的基本运算有三种:入栈、退栈与读栈顶元素。9.队列主要有两种基本运算:入队运算与退队运算。10.在实际应用中,带链的栈可以用来收集计算机存储空间中所有空闲的存储结点,这种带链的栈称为可利用栈。11.栈和队列通常采用的存储结构是链式存储和顺序存储。12.循环队列主要有两种基本运算:入队运算与退队运算。每进行一次入队运算,队尾
8、指针就进 1。13.当循环队列非空且队尾指针等于队头指针时,说明循环队列已满,不能进行入队运算。这种情况称为上溢。14.当循环队列为空时,不能进行退队运算,这种情况称为下溢。15.在一个容量为 25的循环队列中,若头指针 front=16,尾指针 rear=9,则该循环队列中共有 18个元素。注:当 rearfront时,元素个数rearfront。第四部分1、链表反转(无表头结点)单向链表的反转是一个经常被问到的一个面试题,也是一个非常基础的问题。比如一个链表是这样的:1-2-3-4-5 通过反转后成为 5-4-3-2-1。最容易想到的方法遍历一遍链表,利用一个辅助指针,存储遍历过程中当前指
9、针指向的下一个元素,然后将当前节点元素的指针反转后,利用已经存储的指针往后面继续遍历。源代码如下:法一:typedef struct LNodeint data;LNode *next; LNode, *LinkList;void Reverse(LinkList 还有一种利用递归的方法。这种方法的基本思想是在反转当前节点之前先调用递归函数反转后续节点。不过,这个方法有一个缺点,就是在反转后的最后一个结点会形成一个环,所以必须将函数返回的节点的 next 域置为 NULL。因为要改变 head 指针,所以我用了引用。算法的源代码如下:法二:LNode* Reverse(LNode *p, Li
10、nkList return p;LNode *pre, *cur, *nex;pre = head;cur = head-next;while (cur != NULL)nex = cur-next;cur-next = pre;pre = cur;cur = nex;head-next = NULL;head = pre;LNode *p, *q;p = head;head = NULL;while (p != NULL)q = p;p = p - next;q-next = head;head = q;比较elseLNode *tmp = Reverse(p-next, head);tmp
11、-next = p;p-next = NULL;return p;2.判断一个链表是否存在环,例如下面这个链表就存在一个环:例如 N1-N2-N3-N4-N5-N2就是一个有环的链表,环的开始结点是 N5这里有一个比较简单的解法。设置两个指针 p1,p2。每次循环 p1向前走一步,p2向前走两步。直到 p2碰到 NULL指针或者两个指针相等结束循环。如果两个指针相等则说明存在环。求环长:按照上面两个指针不同步长步进的方法,第一次相遇时记录当前指针,步长为 1 的指针继续走,计数,直到再次来到记录的指针,经过的步数即为环长。找环入口:根据所得环长 Y,设置指针指向头部,另一指针先向前走 Y。若两
12、指针当前指向的 node 相同,则为入口,否则各自向前走 1 再判断是否相等。struct Nodeint data;Node *next;bool IsLoop(Node *head)Node *p1 = head,*p2 = head;if (head = NULL | head-next = NULL)return false;dop1 = p1-next;p2 = p2-next-next; while (p2 if (p1 = p2)return true;elsereturn false;3.判断两个数组中是否存在相同的数字:给定两个排好序的数组,怎样高效地判断这两个数组中存在相同
13、的数字?这个问题首先想到的是一个 O(nlogn)的算法。就是任意挑选一个数组,遍历这个数组的所有元素,遍历过程中,在另一个数组中对第一个数组中的每个元素进行 binary search。用 C+实现代码如下:bool FindCommon(int a, int size1, int b, int size2)int i;for (i = 0; i bj)j+;if (ai max)max = v;return max;那怎样才能达到线性复杂度呢?这里运用动态规划的思想。先看一下源代码实现:int MaxSub2(int a, int size)int i, max = 0, tempSum
14、= 0;for (i = 0; i max)max = tempSum;else if (tempSum #include #include using namespace std;/ reverse the string s1 except the substring token.const char* reverse(const char *s1, const char *token)assert(s1 stack cStack;const char *pToken= token, *head = s1, *rear = s1;while (*head != 0)while(*head != 0 head+;if (*pToken = 0) / contain the tokenconst char *p;for(p=head-1;p=rear;p-)cStack.push(*p);pToken = token;rear = head;