数据结构基础例题

墨蓝 2022-12-21 15:53 186阅读 0赞

1.假设有如下遗产继承规则:丈夫和妻子可以相互继承遗产;子女可以继承父亲或母亲的遗产;子女之间不能相互继承。则表示该遗产继承关系的数据结构应该是(B)。

A树 **B****图** C线性表 D集合

2.设输入序列为1、2、3、4、5、6,则通过栈的作用后可以得到的输出序列为(B)。

A.5.3,4,6,1,2

**B.3,2,5,6,4,1**

C.3,1,2,5,4,6

D.1,5,4,6,2,3

3.设有两个串p和q,求q在p中首次出现的位置的运算称作(C)。

A.链接

B.求子串

**C.****模式匹配**

D.求串长

**答案解析**

\[分析\]子串的定位操作通常称作串的模式匹配，是各种串处理系统中最重要的操作之一，算法的基本思想是：从主串的开始字符起，与模式的第一个字符比较，若相等，则继续比较后续字符，否则从主串的下一个字符起再重新与模式的字符比较，依次类推，直至模式中的每一个字符依次和主串中的一个连续的字符序列相等，称匹配成功，否则称匹配不成功。

4.设有6个结点的无向图，该图至少应有（A）条边才能确保是一个连通图。

**A.5**

B.6

C.7

D.8

5.程序段

for(i=n-1;i>=1;i--)

for(j=1;j<=i;j++)

if(A\[j\]>A\[j+1\])

A\[j\]与A\[j+1\]对换

则最后一行的语句频度在最坏情况下是(D)

1.  O(n)
2.  O(nlogn)
3.  O(n^3)
4.  **O(n^2)**

6.在一个单链表中，已知q所指结点是p所指结点的直接前驱，若在q和p之间插入s所指结点，则执行（B）操作。

A.s->next=p->next;p->next=s;

**B.q->next=s;s->next=p;**

C.p->next=s->next;s->next=p;

D.p->next=s;s->next=q;

7.X=(A+B)\*(C-D/E)的后缀式表示为（A）

**A.XAB+CDE/-x=**

BXAB+C-DE/×=

C.XAB+CDE-/ ×=

D.XAB+CD-E/×=

8.下列字符串中，（D）最大

A.Data Structures

B.Link Stack

C.WuYi University

**D.Wuyi University**

9.数组A\[0..5,0..6\]的每个元素占5个字节,将其按列优先次序存储在起始地址为1000的内存单元中,则元素A\[5,5\]的地址是(A)。

**A.1175**

B.1180

C.1205

D.1210

10.输入受限的双端队列是指元素只能从队列的一端输入、但可以队列的两端输出，如下图所示。若有8、1、4、2依次进入输入受限的双端队列,则得不到输出序列(D)。

![20201116231757590.png][]

A.2、8、1、4

B.1、4、8、2

C.4、2、1、8

**D.2****、1****、4****、8**

11.已知一棵二叉树的结点数为n,若该二叉树无度为1的结点,则该二叉树的叶子结点数为(D)。

A.n

B.n-1

C.(n-1)/2

**D.(n+1)/2**

12.假设将线性表L存储在以head为头指针的不带头结点的单链表中,则当\[填空1\]时,表示线性表L是空表。假设将线性表L存储在以head为头指针的带头结点的单链表中,则当\[填空2\]时,表示线性表L是空表。

**\[****填空1\]head=NULL**

**\[****填空2\]head->next=NULL**

1.  在循环双链表的p所指结点后插入s所指结点的操作是

s->prior=\[填空1\];

s->next=\[填空2\];

p->next->prior=s;

p->next=\[填空3\];

**\[****填空1\]p**

**\[****填空2\]p->next**

**\[****填空3\]s**

14.在一个单链表中p所指结点之后插入一个s所指结点时，应执行s- >next=\[填空1\]和

p->next=\[填空2\]的操作。

**\[****填空1\]p->next**

**\[****填空2\]s**

15.数组Q\[n\]用来表示一个循环队列，front为当前队头的前一个位置，rear为队尾元素的位置，计算队列中元素个数的公式为\[填空1\]。

**\[****填空1\](rear-front+n)%n**

16.设输入序列为a、b、c，则经过栈的作用后可以得到5种不同的输出序列,它们是cba, abc, bca,bac和\[填空1\]，不可能得到的序列是\[填空2\]。

**\[****填空1\]acb**

**\[****填空2\]cab**

17.对于含有n个结点的完全二叉树，如果从1开始，按照层序顺序对该树的结点进行编号，则编号为i的结点有左孩子的话，它的左孩子的编号一定是\[填空1\]。

**\[****填空1\]2i**

18.设一棵完全二叉树具有1000个结点，则此完全二叉树有\[填空1\]个度为0的结点，有\[填空2\]个度为2的结点，有\[填空3\]个度为1的结点。

**\[****填空1\]500**

**\[****填空2\]499**

**\[****填空3\]1**

19.在如下数组A中存储了一个静态链表，表头指针为A\[0\].next,试写出该线性表。

![20201116231757598.png][]

**\[****填空1\]78**

**\[****填空2\]50**

**\[****填空3\]40**

**\[****填空4\]60**

**\[****填空5\]34**

**\[****填空6\]90**

20.设完全二叉树的顺序存储结构中存储数据ABCDE,该二叉树的前序遍历序列为\[填空1\],中序遍历序列为\[填空2\]和后序遍历序列为\[填空3\]。

**\[****填空1\]ABDEC**

**\[****填空2\]DBEAC**

**\[****填空3\]DEBCA**

21.试给出下面稀疏矩阵A的三元组表示，下标从0开始。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTk4NzAxNg_size_16_color_FFFFFF_t_70][]

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTk4NzAxNg_size_16_color_FFFFFF_t_70 1][]

\[填空1\]0 \[填空2\]2 \[填空3\]1

\[填空4\]0 \[填空5\]4 \[填空6\]8

\[填空7\]2 \[填空8\]1 \[填空9\]4

\[填空10\]2 \[填空11\]3 \[填空12\]3

\[填空13\]3 \[填空14\]0 \[填空15\]6

\[填空16\]5 \[填空17\]1\[填空18\]5

\[填空19\]7

\[填空20\]6

\[填空21\]6

**0;2;1**

**0;4;8**

**2;1;4**

**2;3;3**

**3;0;6**

**5;1;5**

**7;6;6**

22.已知一个连通图如下图所示，试给出图的邻接矩阵示意图，若从顶点v1出发对该图进行遍历，分别给出基于存储结构的深度优先遍历的顶点序列:\[填空1\]，广度优先遍历的顶点序列:\[填空2\]。注︰用数字表示对应的顶点，如1表示顶点v1，用空格隔开。

![20201116231757723.png][]

**123546**

**124635**

23.设给定一个权值集合w=(3,5,7,9,11)，要求根据给定的权值集合构造一棵哈夫曼树，并求出该哈夫曼树的带权路径长度WPL以及元素9的哈夫曼编码。

注∶请用文字或上传图片作答。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTk4NzAxNg_size_16_color_FFFFFF_t_70 2][]![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTk4NzAxNg_size_16_color_FFFFFF_t_70 3][]

24.为便于存储和处理一般树结构形式的信息,常采用孩子—兄弟表示法将其转换成二叉树(左孩子关系表示父子、右孩子关系表示兄弟)，将下图所示的树转换成对应的二叉树。

注:请用文字或上传图片作答。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTk4NzAxNg_size_16_color_FFFFFF_t_70 4][]

![20201116231757808.png][]

[20201116231757590.png]: /images/20221120/4452c4e6fe074a30add1ac99eb0f5b10.png
[20201116231757598.png]: /images/20221120/5dcfc9362abc447b8fb0735515acf84b.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTk4NzAxNg_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20201116231757594.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTk4NzAxNg==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTk4NzAxNg_size_16_color_FFFFFF_t_70 1]: https://img-blog.csdnimg.cn/20201116231757924.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTk4NzAxNg==,size_16,color_FFFFFF,t_70
[20201116231757723.png]: https://img-blog.csdnimg.cn/20201116231757723.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTk4NzAxNg_size_16_color_FFFFFF_t_70 2]: https://img-blog.csdnimg.cn/20201116231757851.jpeg?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTk4NzAxNg==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTk4NzAxNg_size_16_color_FFFFFF_t_70 3]: https://img-blog.csdnimg.cn/20201116231758141.jpeg?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTk4NzAxNg==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTk4NzAxNg_size_16_color_FFFFFF_t_70 4]: https://img-blog.csdnimg.cn/20201116231757845.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTk4NzAxNg==,size_16,color_FFFFFF,t_70
[20201116231757808.png]: https://img-blog.csdnimg.cn/20201116231757808.png