|
一、选择题
1.在线性结构中，第一个结点没有前驱结点，其余每个结点有且只有 （ A ） 个前驱结点；最后一个结点没有后继结点，其余每个结点有且只有（ ?）个后继结点。?
A. 1 , 1 ??? ?B. 1 , 2 ??? ??? ?C. 2 , 1 ?? ??? ??? ?D. ?2 , 2
2.线性表若采用链式存储结构时，要求内存中可用存储单元的地址_D__。
A. 必须是连续的 ? ? ? ? ? ? ? ? ?B. 部分地址必须是连续的
C. 一定是不连续的 ? ? ? ? ? ? ? ?D. 连续或不连续都可以
3.指针变量p指向单链表中的结点，若该结点是链表的尾结点，下面正确的说法是(A )。
A. ?p->next = = NULL ? ? ?? ?B. ?p->next != NULL
C. ?p = =NULL ? ?? ??? ??? ?D. ?p->next->next = =NULL
4.设指针p所指结点不是单链表的尾结点，删除p所指结点的后继结点的操作是（ D ）。
A. ?p->next=p->next->next; delete p; ? ? ?? ?B. ?? ?q=p->next; p->next=q->next; delet p->next;
C. ?p->next=p-next->next; delet p->next; ?? ?D. ?? ?q=p->next; p->next=q->next; delete q;
5.链表不具备的特点是 _A___ 。
A 可随机访问任何一个元素?? ??? ?B 插入、删除操作不需要移动元素
C 无需事先估计存储空间大小?? ??? ?D 所需存储空间与线性表长度成正比
6.假定栈用单链表的存储结构表示，栈顶指针为top，指向头结点。则进行出栈时执行的操作是( D )。
A. top->next=top; ?B. top=top->data; C. top=top->next; ?D. top->next=top->next->next;
7.一个队列的数据入列序列是1，2，3，4，则队列的出队时输出序列是_B___ 。
A ?4，3，2，1 ? ? ? ?B ?1，2，3，4 ? ? C ?1，4，3，2 ? ? ? ?D ?3，2，4，1
8.栈与一般线性表区别主要在方面 ? D ? 。
A 元素个数 ?? ?B 元素类型 ?? ?C 逻辑结构 ?? ?D 插入、删除元素的位置
9.在一个链队中，假设F和R分别是队首和队尾指针，则删除一个结点的运算是 ?C ?。 ?
A ?R=F->next; ??? ?B ?R=R->next; ??? ?C ?F=F->next; ??? ??? ?D ?F=R->next;
10.?? ?数据三种最主要的逻辑结构是线性结构和（ B ?）。
? ? ?A. 线性表、树 ??? ? ? ?B. 树形结构、图状结构 ??? ??? ?
? ? ?C. 线性表、图 ?? ??? ?D. 树形结构、堆
二、填空题
1.数据结构的存储结构包括：顺序存储表示、 ?链式 存储表示、索引存储表示和散列存储表示等四大类。
2.在线性结构中，第一个结点没有 前驱 ?结点，其余每个结点有 ?1个前驱结点；最后一个结点没有 ?后继 ?结点，其余每个结点有 1 个后继结点。
3.实现字符串逆序（既输入如“ABC”，输出为“CBA”）选用 栈 ?数据结构来解决较好
4.银行柜面服务遵循“先来先服务”的原则，抽号服务终端机采用 ?队列 ? 数据结构来模拟这种行为
5.线性表第一个元素的存储地址是100,每个元素的长度是2,则第5个元素的地址是: 108 ??
6.引起循环队列（队首位置）发生变化的操作是 ? 出队 ??
7.链式队列与顺序队列相比，一个明显的优点是通常不会出现 ? 队满 ? ? ??
8.在一个长度为n的顺序表中删除第i个元素，要移动 ?n-i ?个元素。如果要在第i个元素前插入一个元素，要后移 n-i+1 ? 个元素。?
9.栈操作数据的原则是 “后进先出” ? ?，队列操作数据的原则是 “先进先出” ? ?。
10.在栈中，可进行插入和删除操作的一端称 ?栈顶 ? ? 。
11.栈和队列都是__线性__结构；对于栈只能在__栈顶__插入和删除元素；对于队列只能在__队尾__插入元素和__队首 __删除元素。
12.计算机在运行递归程序时，要用到 ?栈 ? ?结构。?? ??? ?
13.设将整数1，2，3，4进栈，若入、出栈次序为Push, Pop,Push,Push, Pop, Pop,Push, Pop,则出栈的数字序列为 ?1、3、2、4 ? ? ?；若想得到出栈序列1432则具体操作为：Push，Pop, Push，Push，Push，Pop, Pop,Pop ? ? ? ? ? ? ? ? ? ? ? ? ? ? ??
14.在采用少用一个存储空间的具有n个单元的循环队列中，队满时共有n-1 ? ? ? ?个元素。对于下图所示的循环队列，队满的条件是 ? (Q.rear + 1) % n == Q.front ? ? ? ? ?；队空的条件是 ?front==rear ? ? ? ?
三、设计题 ??
1.已知str是一个非空字符串，编写算法通过在临时栈S和队列Q中缓存数据，判处字符串str是否为回文，算法采用文字描述。
创建栈S和队列Q，将字符串str分别从头到尾依次进入栈内S和插入队列Q尾部，然后，栈S依次出栈并和队列Q出队的值相比，直到两个值不相等返回false或者Q.front==Q.rear即全部比较完毕并返回true。
2.设计函数Node * Find(Node *Head, int item)，Head为带头结点单链表的头指针，在传入的链表中查找值为item的结点并返回其地址，如不存在这样的结点则返回空值NULL。?
其中结点的类型声明如下：
struct Node
{ ?
?? ?int data; ?
?? ?Node *next;?
};
Node * Find(Node *Head, int item){
int i = 0;?
? if (Head->next==NULL) {
? ? cout << "顺序表为空表，无法查找！" << endl;
? ? return NULL;
? }
? while (Head->next->next!=NULL&& Head->next->data != item)
*Head = *(Head->next);
? if (Head->next!=NULL)?
? ? return Head->next;?
? else
? ? return NULL;
}
Node * Find(Node *Head, int item){
Node *p=Head->next;
while(p!=NULL){
if(p->data==item)
break;
p=p->next;
}
if (p!=NULL)?
? ? return Head->next;?
? else
? ? return NULL;
}
|