河北工业大学考研资料数据结构习题1答案.docx

1、河北工业大学考研资料数据结构习题1答案一 填空1. 衡量算法效率的两个重要指标称为算法的_时间复杂度_和_空间复杂度2. 一个算法应具有有穷性，确定性，可行性，输入和输出这五个特性。3. 线性表的长度是指_表中元素的个数_。4. 在线性表的顺序存储中，元素之间的逻辑关系是通过元素存储的相对位置决定的；在线性表的链接存储中，元素之间的逻辑关系是通过相关元素的存储位置决定的。5 在双向链表中，每个结点包含两个指针域，一个指向其直接前趋结点，另一个指向其直接后继结点。二、 判断题 1线性表的逻辑顺序与存储顺序总是一致的。(FALSE) 2顺序存储的线性表可以按序号随机存取。(TRUE) 3在线性表的

2、顺序存储结构中，逻辑上相邻的两个元素在物理位置上并不一定紧邻。（FALSE） 4在线性表的链式存储结构中，逻辑上相邻的元素在物理位置上不一定相邻。（TRUE） 5在线性表的顺序存储结构中，插入和删除时，移动元素的个数与该元素的位置有关。（TRUE） 6线性表的链式存储结构是用一组任意的存储单元来存储线性表中数据元素的。（TRUE） 三、 单选题 (请从下列A，B，C，D选项中选择一项) 1线性表是( ) 。 (A) 一个有限序列，可以为空； (B) 一个有限序列，不能为空； (C) 一个无限序列，可以为空； (D) 一个无序序列，不能为空。 答：A 2对顺序存储的线性表，设其长度为n，在任何位

3、置上插入或删除操作都是等概率的。插入一个元素时平均要移动表中的（ ）个元素。 (A) n/2 (B)（n+1）/2 (C) (n 1)/2 (D) n 答：A 3线性表采用链式存储时，其地址( ) 。 (A) 必须是连续的； (B) 部分地址必须是连续的； (C) 一定是不连续的； (D) 连续与否均可以。 答：D 4用链表表示线性表的优点是 （ ）。 (A)便于随机存取 (B)花费的存储空间较顺序存储少 (C)便于插入和删除 (D)数据元素的物理顺序与逻辑顺序相同 答：C 5. 某链表中最常用的操作是在最后一个元素之后插入一个元素和删除最后一个元素，则采用( )存储方式最节省运算时间。 (A

4、)单链表 (B)双链表 (C)单循环链表 (D)带头结点的双循环链表 答：D 6. 循环链表的主要优点是( ) 。 (A)不再需要头指针了 (B)已知某个结点的位置后，能够容易找到他的直接前趋 (C)在进行插入、删除运算时，能更好的保证链表不断开 (D)从表中的任意结点出发都能扫描到整个链表 答：D 7. 单链表中，增加一个头结点的目的是为了（ ）。 (A) 使单链表至少有一个结点 (B)标识表结点中首结点的位置 （C）方便运算的实现 (D) 说明单链表是线性表的链式存储 答：C 8. 若某线性表中最常用的操作是取第i个元素和找第i个元素的前趋元素，则采用（ ）存储方式最节省运算时间（ ）。

5、(A) 单链表 (B) 顺序表 (C) 双链表 (D) 单循环链表 答：B四、简答题1何时选用顺序表、何时选用链表作为线性表的存储结构为宜?答：在实际应用中，应根据具体问题的要求和性质来选择顺序表或链表作为线性表的存储结构，通常有以下几方面的考虑：1.基于空间的考虑。当要求存储的线性表长度变化不大，易于事先确定其大小时，为了节约存储空间，宜采用顺序表；反之，当线性表长度变化大，难以估计其存储规模时，采用动态链表作为存储结构为好。2.基于时间的考虑。若线性表的操作主要是进行查找，很少做插入和删除操作时，采用顺序表做存储结构为宜；反之，若需要对线性表进行频繁地插入或删除等的操作时，宜采用链表做存储

6、结构。并且，若链表的插入和删除主要发生在表的首尾两端，则采用尾指针表示的单循环链表为宜。2在顺序表中插入和删除一个结点需平均移动多少个结点?具体的移动次数取决于哪两个因素?答：在等概率情况下，顺序表中插入一个结点需平均移动n/2个结点。删除一个结点需平均移动(n-1)/2个结点。具体的移动次数取决于顺序表的长度n以及需插入或删除的位置i。i越接近n则所需移动的结点数越少。3 为什么在单循环链表中设置尾指针比设置头指针更好?答：尾指针是指向终端结点的指针，用它来表示单循环链表可以使得查找链表的开始结点和终端结点都很方便，设一带头结点的单循环链表，其尾指针为rear，则开始结点和终端结点的位置分别

7、是rear-next-next和rear,查找时间都是O(1)。若用头指针来表示该链表，则查找终端结点的时间为O(n)。五、分别设计算法，实现线性表的顺序存储结构和链式存储结构的原地置逆。顺序存储结构的原地置逆typedef struct ElemType *elem; /存储空间基址 int length; /线性表的实际长度 int listsize； /当前分配的存储容量， /（以sizeof（ElemType）为单位sqList;void reverse(SqList &A) /顺序表的就地逆置 int i; int j; for(i=1,j=A.length;ij;i+,j-) A.

8、elemiA.elemj;/reverse链式存储结构的原地置逆。算法：ypedef struct LNodeElemType data; /结点值 struct LNode *next; /指针域，存储下一个结点的地址LNode,*LinkList;void ReverseList( LinkList &L )/ 将L 所指的带头结点的单链表逆置if( L-next & L-next-next)/当链表不是空表或单结点时 p=L-next;q=p-next; p - next=NULL; /将开始结点变成终端结点 while (q) /每次循环将后一个结点变成开始结点 p=q; q=q-ne

9、xt ; p-next = L- next ;L-next = p;作业2.1,2.2答案见习题册后面答案2. 6答案：解答： a.（4）（1）b.（7）（11）(8)（4）（1） c.（5）（12）d.（11）（9）（1）（6） 或 (11)（9）（4）（1）2.7答案：解答： a.（11）（3）（4） b.（10）（12）（8）（10）（3）（4） c. （10）（12）（7）（3）（4）d.（12）（11）（3）（14） e.（9）（11）（3）(14)2.8 已知P结点是双向链表的中间结点，试从下列提供的答案中选择合适的语句序列。 a在P结点后插入S结点的语句序列是-。 b在P结点前插

10、入S结点的语句序列是-。 c删除P结点的直接后继结点的语句序列是-。 d删除P结点的直接前驱结点的语句序列是-。 e删除P结点的语句序列是-。 (1)P-next=P-next-next; (10) P-prior-next=P; (2)P-prior=P-prior-prior; (11) P-next-prior =P; (3) P-next=S; (12)P-next-prior=S; (4) P-prior=S; (13) P-prior-next=S; (5)S-next=P; (14) P-next-prior=P-prior (6)S-prior=P; (15)Q=P-next;

11、 (7) S-next= P-next; (16)Q= P-prior; (8) S-prior= P-prior; (17)free(P); (9) P-prior-next=p-next; (18)free(Q);解答： a.（12）（7）（3）（6） 3必须在12和7的后面，其余的顺序可变b.（13）（8）（4）（5） 同上c.（15）（1）（11）（18） 不可变d.（16）（2）（10）（18） 不可变e.（9）（14）（17）2.31答案：ypedef struct LNode ElemType data; /结点值 struct LNode *next; /指针域，存储下一个结点

12、的地址LNode,*LinkList;Status Delete_Pre(linklist s ElemType e) /删除单循环链表中结点s的直接前驱p=s;while(p-next-next!=s) p=p-next; /找到s的前驱的前驱pq=p-next; p-next =s; e=q -data; free(q);return OK;/Delete_Pre 4章 一、填充题 1、一个串中任意个 的字符组成的子序列称为该串的子串。 连续2、串的静态存储结构中的两种不同的存储方式分别是 格式和 格式。 非紧缩 紧缩3、两个串的相等，是指两个两串的 相等， 相同。 长度 对应位置的字符4

13、、已知二维数组A有m行n列，采用行优先方式存储，每个数据元素占k个存储单元，并且第一个元素的存储地址是LOC(A1,1)，则数据元素Ai,j的地址是 。 LOC(A1,1)+(n(i-1)+(j-1)k5、有一个10阶的对称矩阵，采用以行优先的压缩存储方式，已知元素A1,1的地址为1，则元素A8,5的地址是 ，元素A5,8的地址是 。 33 336、广义表(a,(a,b),d,e,(i,j),k)的长度是 ，深度是 。 5 3二、单选题 1、给出字符串A=abcd，它的子串个数是 。 A、10 B、9 C、11 D、14 C 2、给出两个串A=ABCDE，B=ABCdE，它们的关系是不是 。

14、A、B串大于A串 B、B串等于A串 C、B串小于A串 D、B串是A串的子串 A 3、设有两个串A和B，求B在A中首次出现的位置的操作称作 。 A、连接 B、求串长 C、模式匹配 D、求子串 C 4、设串S1=ABCDEFG，串S2=PQRST，函数con(x,y)返回x和y串的连接串，函数subs(s,i,j) 返回串s的从序号i的字符开始的j个字符组成的子串，而函数len(s) 则返回串s 的长度。那么，表达式con(subs(S1,2,len(S2),subs(S1,len(S2),2)的结果串是 。 A、BCDEF B、BCDEFG C、BCPQRST D、BCDEFEF D 5、数组通

15、常具有的两种基本操作是 。 A、建立与删除 B、索引与修改 C、查找与修改 D、查找与索引 C 6、在数组A中，每个数据元素Ai,j的长度为3个字节，数组A的行下标i从1到8，而列下标j从1到10，从首地址SA开始连续存放在存储器中，若该数组按行优先存放时，数据元素A8,5的起始地址为 。 A、SA+141 B、SA+144 C、SA+225 D、SA+222 D7.设有一个10阶的对称矩阵A，采用压缩存储方式，以行序为主存储，a11为第一元素，其存储地址为1，每个元素占一个地址空间，则a85的地址为（E ）。A. 13 B. 33 C. 18 D. 40 E.12 8. 将一个A100100

16、的三对角矩阵，按行优先存入一维数组B1298中，A中元素A6665（即该元素下标i=66，j=65），在B数组中的位置K为（ A ）。A. 198 B. 195 C. 1979. 若对n阶对称矩阵A以行序为主序方式将其下三角形的元素(包括主对角线上所有元素)依次存放于一维数组B1.(n(n+1)/2中，则在B中确定aij（ij）的位置k的关系为( A )。A. i*(i-1)/2+j B. j*(j-1)/2+i C. i*(i+1)/2+j D. j*(j+1)/2+i10. 对稀疏矩阵进行压缩存储目的是（ C ）。A便于进行矩阵运算 B便于输入和输出 C节省存储空间 D降低运算的时间复杂度

17、11. 已知广义表LS(a,b,c),(d,e,f),运用head和tail函数取出LS中原子e的运算是( C )。 A. head(tail(LS) B. tail(head(LS)C. head(tail(head(tail(LS) D. head(tail(tail(head(LS)12. 广义表（a,(b,c),d,e）的表头为（ A ）。 A. a B. a,(b,c) C. (a,(b,c) D. (a)4.24void HString_Concat(HString &t ,HString s1,HString s2) /将堆结构表示的串s1和s2连接为新串tif(t.ch) fr

18、ee(t.ch);if(!(t.ch=(char*)malloc(s1.length+s2.length)*sizeof(char); exit (OVERFLOW); for(i=1;i=s1.length;i+) t.chi-1=s1.chi-1;for(j=1;j=s2.length;j+,i+) t.chi-1=s2.chj-1;t.length=s1.length+s2.length;/HString_Concat 5.23typedef struct int j; int e; DSElem; typedef structDSElem dataMAXSIZE;int cpotMAX

19、ROW; /这个向量存储每一行在二元组中的起始位置int mu,nu,tu; DSMatrix; /二元组矩阵类型 Status DSMatrix_Locate(DSMatrix A,int i,int j,int &e)/求二元组矩阵的元素Aij的值efor(s=A.cpoti;sA.cpoti+1&A.datas.j!=j;s+);/注意查找范围if(sA.cpoti+1&A.datas.j=j) /找到了元素ije=A.datas;return OK;return ERROR;/DSMatrix_Locate第7章 图一、选择题1对于一个具有n个顶点和e条边的有向图，在用邻接表表示图时，

20、拓扑排序算法时间复杂度为（）A） O(n) B） O(n+e) C） O(n*n) D） O(n*n*n) 【答案】B2设无向图的顶点个数为n，则该图最多有（）条边。A）n-1 B）n(n-1)/2 C） n(n+1)/2 D）n2【答案】B3连通分量指的是（）A） 无向图中的极小连通子图B） 无向图中的极大连通子图C） 有向图中的极小连通子图D） 有向图中的极大连通子图【答案】B4n个结点的完全有向图含有边的数目（）A）n*n B）n（n+1） C）n/2 D）n*（n-1）【答案】D5关键路径是（）A） AOE网中从源点到汇点的最长路径 B） AOE网中从源点到汇点的最短路径C） AOV网

21、中从源点到汇点的最长路径D） AOV网中从源点到汇点的最短路径【答案】A6有向图中一个顶点的度是该顶点的（）A）入度 B） 出度 C） 入度与出度之和 D） （入度+出度）/2【答案】C7有e条边的无向图，若用邻接表存储，表中有（）边结点。 A） e B） 2e C） e-1 D） 2(e-1)【答案】B8实现图的广度优先搜索算法需使用的辅助数据结构为（） A） 栈 B） 队列 C） 二叉树 D） 树【答案】B9实现图的非递归深度优先搜索算法需使用的辅助数据结构为（） A） 栈 B） 队列 C） 二叉树 D） 树【答案】A10存储无向图的邻接矩阵一定是一个（） A） 上三角矩阵 B）稀疏矩阵

22、C） 对称矩阵 D） 对角矩阵【答案】C11在一个有向图中所有顶点的入度之和等于出度之和的（）倍 A） 1/2 B）1 C） 2 D） 4【答案】B12在图采用邻接表存储时，求最小生成树的 Prim 算法的时间复杂度为（）A） O(n) B） O(n+e) C） O(n2) D） O(n3)【答案】B13下列关于AOE网的叙述中，不正确的是（）A）关键活动不按期完成就会影响整个工程的完成时间B）任何一个关键活动提前完成，那么整个工程将会提前完成C）所有的关键活动提前完成，那么整个工程将会提前完成D）某些关键活动提前完成，那么整个工程将会提前完成【答案】B14具有10个顶点的无向图至少有多少条边

23、才能保证连通（）A） 9 B）10 C） 11 D） 12【答案】A15在含n个顶点和e条边的无向图的邻接矩阵中，零元素的个数为（）A） e B）2e C） n2-e D）n2-2e【答案】D 16.对于一个具有n个顶点和e条边的无向图，如果采用邻接表来表示，则其表头向量的大小为 。 A、n B、n+1 C、n-1 D、n+e 【答案】 A二、填空题1无向图中所有顶点的度数之和等于所有边数的_倍。【答案】22具有n个顶点的无向完全图中包含有_条边，具有n个顶点的有向完全图中包含有_条边。 【答案】（1）n(n-1)/2 （2） n(n-1)3一个具有n个顶点的无向图中，要连通所有顶点则至少需要

24、_条边。【答案】n-15对用邻接矩阵表示的图进行任一种遍历时，其时间复杂度为_，对用邻接表表示的图进行任一种遍历时，其时间复杂度为_。【答案】（1）O(n2) （2） O(n+e)6对于一个具有n个顶点和e条边的有向图和无向图，在其对应的邻接表中，所含边结点分别为_和_条。【答案】（1）e （2）2e7 在有向图的邻接表和逆邻接表表示中，每个顶点的边链表中分别链接着该顶点的所有_和_结点。【答案】（1）出边 （2） 入边8 对于一个具有n个顶点和e条边的无向图，当分别采用邻接矩阵、邻接表表示时，求任一顶点度数的时间复杂度依次为_和_。【答案】（1）O(n) （2）O(e) 9对于一个具有n个顶

25、点和e条边的连通图，其生成树中的顶点数和边数分别为_和_。【答案】（1）n （2） n-110Prim算法和Kruscal算法的时间复杂度分别为_和_。【答案】（1）O(n2) （2）O(eloge)11. 假设图G中含有n个顶点，e条边，且知每个顶点的度数为di，则它们三者之间满足的关系为： 。 【答案】 e=1/2di12.我们把图中所有顶点加上遍历时经过的所有边构成的子图称为 。【答案】 生成树13、有n个顶点的无向图，其边数最大可达 ，像这样的有最大边数的无向图通常被称为 。【答案】 n(n-1)/2 完全无向图14、树被定义为连通而不具有 的（无向）图。【答案】 回路15、对于一个图

26、G的遍历，通常有两种方法，它们分别是 和 。【答案】 深度优先法 广度优先法16. AOV网中，结点表示活动 ， 边表示活动的先后顺序 ， AOE网中，结点表示事件 ， 边表示活动 .7-16 试对右图所示的AOE网络，解答下列问题。 (1) 这个工程最早可能在什么时间结束。(2) 求每个事件的最早开始时间Vei和最迟开始时间VlI。(3) 求每个活动的最早开始时间e( )和最迟开始时间l( )。 (4) 确定哪些活动是关键活动。画出由所有关键活动构成的图，指出哪些活动加速可使整个工程提前完成。【解答】按拓扑有序的顺序计算各个顶点的最早可能开始时间Ve和最迟允许开始时间Vl。然后再计算各个活动

27、的最早可能开始时间e和最迟允许开始时间l，根据l - e = 0? 来确定关键活动，从而确定关键路径。 1 2 3 4 5 6 Ve 0 19 15 29 38 43 Vl 0 19 15 37 38 43 e 0 0 15 19 19 15 29 38 l 17 0 15 27 19 27 37 38l-e 17 0 0 8 0 12 8 0 此工程最早完成时间为43。关键路径为9章一、填充题1、折半查找法适合于 的数据序列。 有序2、查找表的两种基本类型分别是 和 。 静态查找表 动态查找表3、Hash表查找要研究的两个主要问题分别是 和 。 均匀性 冲突的解决4、在各种查找方法中，平均查找长度与结点个数n无关的查找方法是 。 哈希表查找法5、折半查找的存储结构仅限于 ，而且是 。 顺序存储结构 有序的6、在哈希函数H（key）=key MOD p中，p应取 。 素数7、假设我们在有20个数据元素的有序线性表上实施折半查找，则比较五次查找成功的结点数为 ，平均查找长度为 。 5 3.7(可以画出折半查找判定树)8、在哈希表存储中，装填因子的值越大，则 ，反之装填因子的值越小，则 。 存取元素时发生冲突的可能性就越大 存取元素时发生冲突的可能性就越小二、单选题1、对个结点的线性表进行查找，用顺序查