数据结构常见笔试题.doc

...wd...
...wd...
...wd...
...wd...
...wd...
，为节省时间，应采用〔直接插入排序〕
、可行性、确定性和拥有足够的情报。
...wd...
...wd...
...wd...
第三局部
：一是对数据对象的运算和操作，二是算法的控制构造。
，包括插入、删除、查找、更改等运算，也包括对数据元素进展分析。
。
，线性链表属于(存储构造)。
。
。
、链接、索引等存储构造。
：入栈、退栈与读栈顶元素。
：入队运算与退队运算。
，带链的栈可以用来收集计算机存储空间中所有空闲的存储结点，这种带链的栈称为可利用栈。
。
：入队运算与退队运算。每进展一次入队运算，队尾指针就进1。
，说明循环队列已满，不能进展入队运算。这种情况称为上溢。
，不能进展退队运算，这种情况称为下溢。
，假设头指针front=16，尾指针rear=9，则该循环队列中共有18个元素。注：当rear<front时，元素个数＝总容量－〔front－rear〕；当rear>front时，元素个数＝rear－front。
...wd...
...wd...
...wd...
第四局部
1、链表反转〔无表头结点〕
单向链表的反转是一个经常被问到的一个面试题，也是一个非常根底的问题。比方一个链表是这样的：1->2->3->4->5通过反转后成为5->4->3->2->1。
最容易想到的方法遍历一遍链表，利用一个辅助指针，存储遍历过程中当前指针指向的下一个元素，然后将当前节点元素的指针反转后，利用已经存储的指针往后面继续遍历。源代码如下：
法一：
typedef struct LNode
{
int data;
LNode *next;
} LNode, *LinkList;
void Reverse(LinkList &head)
{
if(head ==NULL)
return;
LNode *p, *q;
p = head;
head = NULL;
while (p != NULL)
{
q = p;
p = p -> next;
q->next = head;
head = q;
}
LNode *pre, *cur, *nex;
pre = head;
cur = head->next;
while (cur != NULL)
{
nex = cur->next;
cur->next = pre;
pre = cur;
cur = nex;
}
head->next = NUL