📄 cs3.htm
字号:
<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"><span style="mso-spacerun:
yes"> </span>5．设单链表中指针p指向结点m，若要删除m之后的结点（若存在），则需修改指针的操作为<u><span style="mso-spacerun: yes">
</span></u>。</span></p>
<p class="MsoPlainText" style="line-height: 150%"><span lang="EN-US"><span style="mso-spacerun: yes">
</span>(A)p->link=p->link->link； B) p=p->link;</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">(C)p=p->link->link；<span style="mso-spacerun: yes">
</span>D) p->link=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%"><span lang="EN-US"><span style="mso-spacerun:
yes"> </span>6．线性表采用链式存储时，其地址<u><span style="mso-spacerun: yes">
</span></u>。</span></p>
<p class="MsoPlainText" style="line-height: 150%"><span lang="EN-US"><span style="mso-spacerun: yes">
</span>(A)必须是连续的</span></p>
<p class="MsoPlainText" style="line-height: 150%"><span lang="EN-US"><span style="mso-spacerun: yes">
</span>(B)一定是不连续的</span></p>
<p class="MsoPlainText" style="line-height: 150%"><span lang="EN-US"><span style="mso-spacerun: yes">
</span>(C)部分地址必须是连续的</span></p>
<p class="MsoPlainText" style="line-height: 150%"><span lang="EN-US"><span style="mso-spacerun: yes">
</span>(D)连续与否均可以</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"><span style="mso-spacerun:
yes"> </span>7.在一个具有n个结点的有序单链表中插入一个新结点使得仍然有序，其算法的时间复杂度为</span></p>
<p class="MsoPlainText" style="line-height: 150%"><span lang="EN-US"><span style="mso-spacerun: yes">
</span>(A)O(10g<sub>2</sub>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(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%">三、应用题</p>
<p class="MsoPlainText" style="text-indent: -18.0pt; mso-list: l1 level1 lfo2; tab-stops: list 18.0pt; line-height: 150%; margin-left: 18.0pt"><span lang="EN-US" style="mso-font-kerning:8.0pt">1、<span style="font:7.0pt "Times New Roman"">
</span></span><span style="mso-font-kerning:8.0pt">试编写一个算法，在带表头结点的单链表中寻找第<i style="mso-bidi-font-style:normal"><span lang="EN-US">i</span></i>个结点。若找到，则函数返回第<i style="mso-bidi-font-style:normal"><span lang="EN-US">i</span></i>个结点的地址；若找不到，则函数返回<span lang="EN-US">0。<o:p>
</o:p>
</span></span></p>
<p class="MsoNormal" style="line-height: 150%"><span lang="EN-US" style="mso-font-kerning:8.0pt"> <o:p>
</o:p>
</span></p>
<p class="MsoNormal" style="text-indent: -18.0pt; line-height: 150%; mso-list: l1 level1 lfo2; tab-stops: list 18.0pt; margin-left: 18.0pt"><span lang="EN-US" style="mso-font-kerning:8.0pt">2、<span style="font:7.0pt "Times New Roman"">
</span></span><span style="font-family:宋体;mso-ascii-font-family:"Times New Roman";
mso-hansi-font-family:"Times New Roman";mso-font-kerning:8.0pt">从左到右及从右到左遍历一个单链表是可能的，其方法是在从左向右遍历的过程中将连接方向逆转，如右图所示。在图中的指针</span><i style="mso-bidi-font-style:normal"><span lang="EN-US" style="mso-font-kerning:
8.0pt">p</span></i><span style="font-family:宋体;mso-ascii-font-family:"Times New Roman";
mso-hansi-font-family:"Times New Roman";mso-font-kerning:8.0pt">指向当前正在访问的结点，指针</span><i style="mso-bidi-font-style:normal"><span lang="EN-US" style="mso-font-kerning:
8.0pt">pr</span></i><span style="font-family:宋体;mso-ascii-font-family:"Times New Roman";
mso-hansi-font-family:"Times New Roman";mso-font-kerning:8.0pt">指向指针</span><i style="mso-bidi-font-style:normal"><span lang="EN-US" style="mso-font-kerning:
8.0pt">p</span></i><span style="font-family:宋体;mso-ascii-font-family:"Times New Roman";
mso-hansi-font-family:"Times New Roman";mso-font-kerning:8.0pt">所指结点的左侧的结点。此时，指针</span><i style="mso-bidi-font-style:normal"><span lang="EN-US" style="mso-font-kerning:
8.0pt">p</span></i><span style="font-family:宋体;mso-ascii-font-family:"Times New Roman";
mso-hansi-font-family:"Times New Roman";mso-font-kerning:8.0pt">所指结点左侧的所有结点的链接方向都已逆转。</span><span lang="EN-US" style="mso-font-kerning:8.0pt"><o:p>
</o:p>
</span></p>
<p class="MsoNormal" style="line-height: 150%"><span lang="EN-US" style="mso-font-kerning:8.0pt"><span style="mso-tab-count:1">
</span>(1) </span><span style="font-family:宋体;mso-ascii-font-family:"Times New Roman";mso-hansi-font-family:
"Times New Roman";mso-font-kerning:8.0pt">编写一个算法，从任一给定的位置</span><span lang="EN-US" style="mso-font-kerning:8.0pt">(<i style="mso-bidi-font-style:normal">pr</i>,
<i style="mso-bidi-font-style:normal">p</i>)</span><span style="font-family:
宋体;mso-ascii-font-family:"Times New Roman";mso-hansi-font-family:"Times New Roman";
mso-font-kerning:8.0pt">开始，将指针</span><i style="mso-bidi-font-style:normal"><span lang="EN-US" style="mso-font-kerning:8.0pt">p</span></i><span style="font-family:
宋体;mso-ascii-font-family:"Times New Roman";mso-hansi-font-family:"Times New Roman";
mso-font-kerning:8.0pt">右移</span><i style="mso-bidi-font-style:normal"><span lang="EN-US" style="mso-font-kerning:8.0pt">k</span></i><span style="font-family:
宋体;mso-ascii-font-family:"Times New Roman";mso-hansi-font-family:"Times New Roman";
mso-font-kerning:8.0pt">个结点。如果</span><i style="mso-bidi-font-style:normal"><span lang="EN-US" style="mso-font-kerning:8.0pt">p</span></i><span style="font-family:
宋体;mso-ascii-font-family:"Times New Roman";mso-hansi-font-family:"Times New Roman";
mso-font-kerning:8.0pt">移出链表，则将</span><i style="mso-bidi-font-style:normal"><span lang="EN-US" style="mso-font-kerning:8.0pt">p</span></i><span style="font-family:
宋体;mso-ascii-font-family:"Times New Roman";mso-hansi-font-family:"Times New Roman";
mso-font-kerning:8.0pt">置为</span><span lang="EN-US" style="mso-font-kerning:8.0pt">0</span><span style="font-family:宋体;mso-ascii-font-family:"Times New Roman";mso-hansi-font-family:
"Times New Roman";mso-font-kerning:8.0pt">，并让</span><i style="mso-bidi-font-style:
normal"><span lang="EN-US" style="mso-font-kerning:8.0pt">pr</span></i><span style="font-family:宋体;mso-ascii-font-family:"Times New Roman";mso-hansi-font-family:
"Times New Roman";mso-font-kerning:8.0pt">停留在链表最右边的结点上。</span><span lang="EN-US" style="mso-font-kerning:8.0pt"><o:p>
</o:p>
</span></p>
<p class="MsoPlainText" style="line-height: 150%"><span lang="EN-US" style="mso-font-kerning:8.0pt"><span style="mso-tab-count:1">
</span>(2) 编写一个算法，从任一给定的位置(<i style="mso-bidi-font-style:
normal">pr</i>, <i style="mso-bidi-font-style:normal">p</i>)开始，将指针<i style="mso-bidi-font-style:normal">p</i>左移<i style="mso-bidi-font-style:normal">k</i>个结点。如果<i style="mso-bidi-font-style:normal">p</i>移出链表，则将<i style="mso-bidi-font-style:
normal">p</i>置为0，并让<i style="mso-bidi-font-style:normal">pr</i>停留在链表最左边的结点上。</span></p>
<div style="mso-element:frame;mso-element-frame-height:5.25pt;mso-element-frame-hspace:
9.0pt;mso-element-wrap:around;mso-element-anchor-vertical:paragraph;mso-element-anchor-horizontal:
page;mso-element-left:130.85pt;mso-element-top:.05pt">
<table cellspacing="0" cellpadding="0" hspace="0" vspace="0" height="7" align="left">
<tr>
<td valign="top" align="left" height="7" style="padding-top:0cm;padding-right:9.0pt;
padding-bottom:0cm;padding-left:9.0pt">
<p class="MsoNormal" style="line-height: 150%; mso-element: frame; mso-element-frame-height: 5.25pt; mso-element-frame-hspace: 9.0pt; mso-element-wrap: around; mso-element-anchor-vertical: paragraph; mso-element-anchor-horizontal: page; mso-element-left: 130.85pt; mso-element-top: .05pt"><span lang="EN-US" style="mso-font-kerning:8.0pt"><!--[if gte vml 1]><v:shapetype
id="_x0000_t75" coordsize="21600,21600" o:spt="75" o:preferrelative="t"
path="m@4@5l@4@11@9@11@9@5xe" filled="f" stroked="f">
<v:stroke joinstyle="miter"/>
<v:formulas>
<v:f eqn="if lineDrawn pixelLineWidth 0"/>
<v:f eqn="sum @0 1 0"/>
<v:f eqn="sum 0 0 @1"/>
<v:f eqn="prod @2 1 2"/>
<v:f eqn="prod @3 21600 pixelWidth"/>
<v:f eqn="prod @3 21600 pixelHeight"/>
<v:f eqn="sum @0 0 1"/>
<v:f eqn="prod @6 1 2"/>
<v:f eqn="prod @7 21600 pixelWidth"/>
<v:f eqn="sum @8 21600 0"/>
<v:f eqn="prod @7 21600 pixelHeight"/>
<v:f eqn="sum @10 21600 0"/>
</v:formulas>
<v:path o:extrusionok="f" gradientshapeok="t" o:connecttype="rect"/>
<o:lock v:ext="edit" aspectratio="t"/>
</v:shapetype><v:shape id="_x0000_i1025" type="#_x0000_t75" style='width:224.25pt;
height:36.75pt' fillcolor="window">
<v:imagedata src="file:///C:/DOCUME~1/wangsj/LOCALS~1/Temp/msoclip1/01/clip_image001.png"
o:title=""/>
</v:shape><![endif]-->
<img src="../tp/cs3.ht1.gif" v:shapes="_x0000_i1025" width="299" height="49"></span></p>
</td>
</tr>
</table>
</div>
<p class="MsoPlainText" style="line-height: 150%"><span lang="EN-US"> <o:p>
</o:p>
</span></p>
</body>
</html>
⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -