📄 cs3.htm
字号:
<html>
<head>
<meta http-equiv="Content-Type" content="text/html; charset=gb2312">
<meta name="GENERATOR" content="Microsoft FrontPage 4.0">
<meta name="ProgId" content="FrontPage.Editor.Document">
<title>第三章 链表</title>
</head>
<body>
<p class="MsoPlainText" align="center" style="text-align: center; line-height: 150%"><b><span style="font-size:14.0pt;mso-bidi-font-size:10.5pt">第三章<span lang="EN-US"><span style="mso-spacerun: yes">
</span>链表<o:p>
</o:p>
</span></span></b></p>
<p class="MsoPlainText" style="line-height: 150%"><b><span lang="EN-US"> <o:p>
</o:p>
</span></b></p>
<p class="MsoPlainText" style="line-height: 150%"><b>一、填空题<span lang="EN-US"><o:p>
</o:p>
</span></b></p>
<p class="MsoPlainText" style="text-indent: -18.0pt; mso-list: l2 level1 lfo1; tab-stops: list 28.5pt; line-height: 150%; margin-left: 28.5pt"><span lang="EN-US">1．<span style="font:7.0pt "Times New Roman"">
</span></span>在线性表的顺序存储中，元素之间的逻辑关系是通过<span lang="EN-US">__l__决定的：在线性表的链接存储中，元素之间的逻辑关系是通过__2__决定的.</span></p>
<p class="MsoPlainText" style="line-height: 150%"><span lang="EN-US"> <o:p>
</o:p>
</span></p>
<p class="MsoPlainText" style="text-indent: 10.5pt; mso-char-indent-count: 1.0; mso-char-indent-size: 10.5pt; line-height: 150%"><span lang="EN-US">2．对于一个具有n个结点的单链表，在已知的结点*p后插入一个新结点的时间复杂度为__1___,在给定值为x的结点后插入一个新结点的时间复杂度为__2__。</span></p>
<p class="MsoPlainText" style="line-height: 150%"><span lang="EN-US"> <o:p>
</o:p>
</span></p>
<p class="MsoPlainText" style="text-indent: 10.5pt; mso-char-indent-count: 1.0; mso-char-indent-size: 10.5pt; line-height: 150%"><span lang="EN-US">3．在双向链表中，每个结点含有两个指针域，一个指向__1__结点，另一个指向__2__结点。</span></p>
<p class="MsoPlainText" style="line-height: 150%"><span lang="EN-US"> <o:p>
</o:p>
</span></p>
<p class="MsoPlainText" style="text-indent: 10.5pt; mso-char-indent-count: 1.0; mso-char-indent-size: 10.5pt; line-height: 150%"><span lang="EN-US">4．在一个单链表中删除*p结点时，完成下列操作：</span></p>
<p class="MsoPlainText" style="line-height: 150%"><span lang="EN-US"><span style="mso-spacerun: yes">
</span>q=p->link：</span></p>
<p class="MsoPlainText" style="line-height: 150%"><span lang="EN-US"><span style="mso-spacerun: yes">
</span>p->data=p—>link—>data;</span></p>
<p class="MsoPlainText" style="line-height: 150%"><span lang="EN-US"><span style="mso-spacerun: yes">
</span>p—>link=___1___</span></p>
<p class="MsoPlainText" style="text-indent: 10.5pt; mso-char-indent-count: 1.0; mso-char-indent-size: 10.5pt; line-height: 150%"><span lang="EN-US"> <o:p>
</o:p>
</span></p>
<p class="MsoPlainText" style="text-indent: 10.5pt; mso-char-indent-count: 1.0; mso-char-indent-size: 10.5pt; line-height: 150%"><span lang="EN-US">5.
若要在一个不带表头结点的单链表的首结点*p结点之前插入一个*s结点时，完成下列操作:</span></p>
<p class="MsoPlainText" style="line-height: 150%"><span lang="EN-US"><span style="mso-spacerun: yes">
</span>s->link=___1____;</span></p>
<p class="MsoPlainText" style="line-height: 150%"><span lang="EN-US"><span style="mso-spacerun: yes">
</span>P->link=s;</span></p>
<p class="MsoPlainText" style="line-height: 150%"><span lang="EN-US"><span style="mso-spacerun: yes">
</span>t=p->data;</span></p>
<p class="MsoPlainText" style="line-height: 150%"><span lang="EN-US"><span style="mso-spacerun: yes">
</span>p->data=____2_____;</span></p>
<p class="MsoPlainText" style="line-height: 150%"><span lang="EN-US"><span style="mso-spacerun: yes">
</span>s->data=____3______;</span></p>
<p class="MsoPlainText" style="line-height: 150%"><span style="mso-spacerun: yes" lang="EN-US"> </span></p>
<p class="MsoPlainText" style="text-indent: 10.5pt; mso-char-indent-count: 1.0; mso-char-indent-size: 10.5pt; line-height: 150%"><span lang="EN-US">6．根据线性表的链式存储结构中每个结点所含指针的个数，链表可分为_1___和__2____；而根据指针的联接方式，链表又可分为___3___和___④___<span style="mso-spacerun: yes">
</span>。</span></p>
<p class="MsoPlainText" style="line-height: 150%"><span style="mso-spacerun: yes" lang="EN-US"> </span></p>
<p class="MsoPlainText" style="text-indent: 10.5pt; mso-char-indent-count: 1.0; mso-char-indent-size: 10.5pt; line-height: 150%"><span lang="EN-US">7．对于线性表的顺序存储，需要预先分配好存储空间，若分配太多容易造成存储空间的___1____，若分配太少又容易在算法中造成__2____，因而只适用于数据量变化不大的情况；对于线性表的链接存储，不需要__3____存储空间，存储器中的整个___4____
都可供使用，分配和回收结点都非常方便，能够有效地利用存储空间，在算法中不必考虑____5____的发生，因而适用于数据量变化较大的情况。</span></p>
<p class="MsoPlainText" style="text-indent: 10.5pt; mso-char-indent-count: 1.0; mso-char-indent-size: 10.5pt; line-height: 150%"><span lang="EN-US"> <o:p>
</o:p>
</span></p>
<p class="MsoPlainText" style="text-indent: 10.5pt; mso-char-indent-count: 1.0; mso-char-indent-size: 10.5pt; line-height: 150%"><span lang="EN-US">8．当对一个线性表经常进行的是存取操作，而很少进行插入和删除操作时，则采用___1____存储结构为宜，相反，当经常进行的是插入和删除操作时，则采用<span style="mso-spacerun: yes">
</span>__②__存储结构为宜。</span></p>
<p class="MsoPlainText" style="line-height: 150%"><span lang="EN-US"> <o:p>
</o:p>
</span></p>
<p class="MsoPlainText" style="text-indent: 10.5pt; mso-char-indent-count: 1.0; mso-char-indent-size: 10.5pt; line-height: 150%"><span lang="EN-US">9．在单链表中设置头结点的作用是<u>
①<span style="mso-spacerun: yes"> </span></u>。</span></p>
<p class="MsoPlainText" style="line-height: 150%"><span lang="EN-US"> <o:p>
</o:p>
</span></p>
<p class="MsoPlainText" style="text-indent: 21.0pt; mso-char-indent-count: 2.0; mso-char-indent-size: 10.5pt; line-height: 150%"><span lang="EN-US">10．顺序表中逻辑上相邻的元素，物理位置<u>
① </u>紧邻，单链表中逻辑上相邻的元素，物理位置__2___紧邻。</span></p>
<p class="MsoPlainText" style="line-height: 150%"><span lang="EN-US"> <o:p>
</o:p>
</span></p>
<p class="MsoPlainText" style="line-height: 150%"><span lang="EN-US"> <o:p>
</o:p>
</span></p>
<p class="MsoPlainText" style="line-height: 150%"><b>二、选择题<span lang="EN-US"><o:p>
</o:p>
</span></b></p>
<p class="MsoPlainText" style="line-height: 150%"><span lang="EN-US">1．从一个具有n个结点的单链表中查找其值等于x的结点时，在查找成功的情况下，需平均比较______个元素结点。</span></p>
<p class="MsoPlainText" style="line-height: 150%"><span lang="EN-US"><span style="mso-spacerun: yes">
</span>(A)n／2<span style="mso-spacerun: yes"> </span>(B)n<span style="mso-spacerun: yes">
</span>(C)(n+1)／2<span style="mso-spacerun:
yes"> </span>(D)(n-1)／2</span></p>
<p class="MsoPlainText" style="line-height: 150%"><span lang="EN-US"> <o:p>
</o:p>
</span></p>
<p class="MsoPlainText" style="line-height: 150%"><span lang="EN-US">2．对一个具有n个元素的线性表，建立其单链表的时间复杂度为_____。</span></p>
<p class="MsoPlainText" style="line-height: 150%"><span lang="EN-US"><span style="mso-spacerun: yes">
</span>(A)O(n)<span style="mso-spacerun: yes"> </span>(B)O(1)<span style="mso-spacerun: yes">
</span>(C)O(n<sup>2</sup>)<span style="mso-spacerun: yes"> </span>(D)O(10g<sub>2</sub>n)</span></p>
<p class="MsoPlainText" style="line-height: 150%"><span lang="EN-US"> <o:p>
</o:p>
</span></p>
<p class="MsoPlainText" style="line-height: 150%"><span lang="EN-US">3．在一个单链表中，已知*q结点是*p结点的前趋结点，若在*q和*p之间插入*s结点，则须执行______.</span></p>
<p class="MsoPlainText" style="line-height: 150%"><span lang="EN-US"><span style="mso-spacerun: yes">
</span>(A)s->link=p->link；p->link=s</span></p>
<p class="MsoPlainText" style="line-height: 150%"><span lang="EN-US"><span style="mso-spacerun: yes">
</span>(B)q->link=s：s->link=p</span></p>
<p class="MsoPlainText" style="line-height: 150%"><span lang="EN-US"><span style="mso-spacerun: yes">
</span>(C)p->link=s->link;<span style="mso-spacerun: yes"> </span>s->link=q;</span></p>
<p class="MsoPlainText" style="line-height: 150%"><span lang="EN-US"><span style="mso-spacerun: yes">
</span>(D)p->link=s：<span style="mso-spacerun: yes"> </span>s->link=q</span></p>
<p class="MsoPlainText" style="line-height: 150%"><span style="mso-spacerun: yes" lang="EN-US"> </span></p>
<p class="MsoPlainText" style="line-height: 150%"><span lang="EN-US">4．在双向循环链表中，在p所指的结点之后插入s指针所指的结点，其操作是——。</span></p>
<p class="MsoPlainText" style="line-height: 150%"><span lang="EN-US">(A)p->link=s；<span style="mso-spacerun: yes">
</span>s->lLink=p；</span></p>
<p class="MsoPlainText" style="line-height: 150%"><span lang="EN-US">(p->link)->lLink=s；s->link=p->link；</span></p>
<p class="MsoPlainText" style="line-height: 150%"><span lang="EN-US">(B)s->lLink=p；<span style="mso-spacerun: yes">
</span>s->link=p->link；</span></p>
<p class="MsoPlainText" style="line-height: 150%"><span lang="EN-US"><span style="mso-spacerun: yes">
</span>p->link=s：<span style="mso-spacerun: yes"> </span>p->link->lLink=s；</span></p>
<p class="MsoPlainText" style="line-height: 150%"><span lang="EN-US">(C)p->link=s；p->link->lLink=s；</span></p>
<p class="MsoPlainText" style="line-height: 150%"><span lang="EN-US"><span style="mso-spacerun: yes">
</span>s->lLink=p；<span style="mso-spacerun: yes"> </span>s->link=p->link~</span></p>
<p class="MsoPlainText" style="line-height: 150%"><span lang="EN-US">(D)S->
lLink =p；<span style="mso-spacerun: yes"> </span>s->link=p->link；</span></p>
<p class="MsoPlainText" style="line-height: 150%"><span lang="EN-US"><span style="mso-spacerun: yes">
</span>p->link->lLink=s；<span style="mso-spacerun: yes"> </span>p->link</span></p>
⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -