《数据结构练习题--2011级--参考答案》由会员分享，可在线阅读，更多相关《数据结构练习题--2011级--参考答案（18页珍藏版）》请在金锄头文库上搜索。
1、. . . 第1章选择题：1.1 数据结构在计算机存中的表示是指：A数据的存储结构 B.数据结构C数据的逻辑结构 D.数据元素之间的关系1.2 数据的逻辑结构是指： A. 数据所占的存储空间量 B各数据元素之间的逻辑关系C. 数据在计算机中顺序或的存储方式D. 存储在存或外存中的数据1.3 在下列的叙述中，正确的是： A数据的逻辑结构是指数据的各数据项之间的逻辑关系。B数据的物理结构是指数据在计算机的实际存储形式。 C在顺序存储结构中，数据元素之间的关系是显示体现的。D存储结构是通过结点的存储位置相邻来体现数据元素之间的关系。填空题：1.4 数据结构主要研究 数据的逻辑结构 ， 数据的存储结构
2、 ， 数据的运算 三个方面的容。1.5 存储的特点是通过附加 指针域 来表示数据元素之间的逻辑关系。1.6 数据结构中讨论的三种经典结构包括： 线性表 ， 树 ， 图 。1.7 数据结构中常用的存储方法有： 顺序 ， ， 索引 ， 散列 。1.8 顺序存储结构可以通过位置 隐含 表示关系，存储结构通过附加指针来 显示 表示关系。1.9 算法的特性包括 有穷性 ， 确定性 ， 可行性 ，输入和输出。1.10 算法性能分析的两个主要定量评价指标是 时间复杂度 和 空间复杂度 。简答题：1.11 数据结构研究的三方面容之间有什么联系和区别？ 数据结构研究的三方面容包括: 数据的逻辑结构、存储结构和运
3、算。数据的逻辑结构是数学模型，存储结构是指逻辑结构到存储区域的映射，运算是定义在逻辑结构上，实现在存储结构上。1.12 简述数据结构中讨论的三种经典结构的逻辑特征是什么？三种经典结构：线性表、树和图。逻辑特征分别为：（1）线性表：一对一。有且仅有一个开始结点和一个终端结点，其余的部结点都有且仅有一个前趋结点和一个后继结点。（2）树：一对多。有且仅有一个开始结点，可有若干个终端结点，其余的部结点都有且仅有一个前趋结点，可以有若干个后继结点。（3）图：多对多。可有若干个开始结点和终端结点，其余的部结点可以有若干个前趋结点和若干个后继结点。1.13 简述各种常用存储方法的基本思想。各种方法的基本思想
4、：顺序存储：逻辑上相邻的数据元素存储在物理位置上相邻的存储单元里。存储：通过附加指针域表示数据元素之间的关系。索引存储：除了存储数据元素，还要建立附加的索引表来标识数据元素的地址。散列存储：根据关键字直接计算出该结点的存储地址，通常称为关键字地址转换法。第2章选择题：2.1 线性表L=（a1，a2，an），下列说确的是：A. 每个元素都有一个直接前驱和一个直接后继。B. 线性表中至少有一个元素。C. 表中元素的排列顺序必须是由小到大或由大到小。D. 除第一个和最后一个元素外，其余每个元素都有且仅有一个直接前驱和一个直接后继。2.2 下面关于线性表的叙述中，错误的是：A线性表若采用顺序存储，必须
5、占用一片连续的存储单元B线性表若采用顺序存储，便于进行插入和删除操作C线性表若采用存储，不必占用一片连续的存储单元D线性表若采用存储，便于插入和删除操作2.3 在长度为n的顺序表的第i(1in+1)个位置上插入一个元素，元素的移动次数为：A .n-i+1 B .n-i C .i D .i-12.4 删除长度为n的顺序表中的第i(1in)个位置上的元素，元素的移动次数为：A. n-i+1 B. n-i C. i D. i-12.5 已知一个带头结点单链表L，在表头元素前插入新结点 *s的语句为：A. L=s; s-next=L; B. s-next=L-next; L-next=s; C. s=
6、L; s-next=L; D. s-next=L; s=L;2.6 已知一个不带头结点单链表的头指针为L，则在表头元素之前插入一个新结点*s的语句为：A. L=s; s-next=L; B. s-next=L; L=s; C. s=L; s-next=L; D. s-next=L; s=L;2.7 已知单链表上一结点的指针为p，则在该结点之后插入新结点*s的正确操作语句为：A p-next=s; s-next=p-next; B s-next=p-next; p-next=s;C p-next=s; p-next=s-next; D p-next=s-next; p-next=s;2.8 已知
7、单链表上一结点的指针为p，则删除该结点后继的正确操作语句是：A s= p-next; p=p-next; free(s); B p=p-next; free(p);C s= p-next; p-next=s-next; free(s);D p=p-next; free(p-next);2.9 设一个链表最常用的操作是在表尾插入结点和在表头删除结点，则选用下列哪种存储结构效率最高？A. 单链表B. 双链表 C. 单循环链表D. 带尾指针的单循环链表2.10 线性表的存储结构是一种（ ）存储结构。A. 随机存取 B. 顺序存取 C. 索引存取 D. 散列存取2.11 链表不具备的特点是：A. 插入
8、删除不需要移动元素 B. 不必事先估计存储空间 C. 可随机访问任一结点 D. 所需空间与其长度成正比填空题：2.1 在单链表L中，指针p所指结点有后继结点的条件是 p-next!=NULL 。2.2 判断带头结点的单链表L为空的条件 L-next=NULL。2.12 顺序表和链表中能实现随机存取的是 顺序表 ，插入、删除操作效率高的是 链表 。2.13 对于一个具有n个结点的单链表，已知一个结点的指针p，在其后插入一个新结点的时间复杂度为 O（1） ；若已知一个结点的值为x，在其后插入一个新结点的时间复杂度为 O（n） 。2.14 顺序表的存储密度 大 ，链表的存储密度 小 。 简答题：2.
9、15 比较顺序表和链表这两种线性表不同存储结构的特点。顺序表存储密度大存储空间连续静态分配随机存取插、删效率低链表存储密度大存储空间可不连续动态分配顺序存取插、删效率高2.16 简述头结点的作用。头结点的作用是使得单链表在表头位置的插、删操作同中间位置的插、删操作完全相同。即使“空表”与“非空表”的操作统一，也使“表头结点”与其他位置结点的操作完全一致，无须特殊处理。2.17 写出单链表存储结构的C语言描述。typedef int DataType; typedef struct Node DataType data; struct Node *next; LinkList;完善程序题：2.1
10、8 设计一个算法，其功能为：向一个带头结点的有序单链表（从小到大有序）中插入一个元素x，使插入后链表仍然有序。请将代码补充完整。typedef int DataType;typedef struct Node DataType data; ; /*定义指向该结构类型的指针变量next*/Linklist;void insert(Linklist *L,DataType x) Linklist *s,*p=L; while(p-next & p-next-datadata=x; ; ; /*将*s结点插入到*p结点的后面*/struct Node * next; p=p-next; s=(Lin
11、kList *)malloc(sizeof(LinkList);s-next=p-next; p-next=s;2.19 设计一个函数功能为：在带头结点的单链表中删除值最小的元素。请将代码补充完整。typedef int DataType;typedef Node /*定义结构体类型*/DataType data;struct Node * next;LinkList;void deleteMin(LinkList *L)LinkList *p=L-next,*q;/*首先查找值最小的元素，指针q指向最小元素结点*/q=p;while(p)if( p-data data)q=p; ; /* p
12、指针后移一步，比较单链表中的每一个结点*/if(!q) return; /*不存在最小结点（空表）时，直接退出*/ p=L; /*若存在最小结点，则先找到最小结点的前驱，即*q的前驱*/while( )p=p-next; ; /*从单链表中删除最小元素结点（指针q所指结点）*/ ; /* 释放指针q所指结点的空间*/structp=p-next;p-next!=qp-next=q-next; free(q);算法设计题：2.20 已知长度为n的线性表A中的元素是整数，写算法求线性表中值大于item的元素个数。分两种情况编写函数：（1）线性表采用顺序存储；（2）线性表采用单链表存储。（1）线性表采用顺序存储#define MAX 1024typedef int DataType;typedef struct DataType dataMAX;int last; SeqList;int LocateElem (SeqList *L, DataType item)int i,j=0; for(i=0;ilast ;i+) if( L-datai item ) j+; return j;（2）线性
