一些数据结构的习题.doc

文档介绍：数据结构习题
第一章 2
第二章 3
第三章 6
第四章 7
第五章 7
第六章 9
第七章 11
第九章 13
第十章 15
十二章文件 16
第一章
一、选择题
,与所使用的计算机无关的数据叫结构。
A. 存储 B. 物理 C. 逻辑 D. 物理和存储
二、判断题
( )。
( )。
三、基本概念
:数据、数据元素、数据类型、数据结构、逻辑结构、存储结构、线
性结构、非线性结构。
2. 常用的存储表示方法有哪几种?
,g,h分别为 f(n)=100n^3+n^2+1000 , g(n)=25n^3+5000n^2 , h(n)=n^+5000nlgn 请判断下列关系是否成立:
(1) f(n)=O(g(n)) 
(2) g(n)=O(f(n)) 
(3) h(n)=O(n^)
(4) h(n)=O(nlgn)
◇ 这里我们复习一下渐近时间复杂度的表示法T(n)=O(f(n)),这里的"O"是数学符号,它的严格定义是"若T(n)和f(n)是定义在正整数集合上的两个函数,则T(n)=O(f(n))表示存在正的常数C和n0 ,使得当n≥n0时都满足0≤T(n)≤C·f(n)。"用容易理解的话说就是这两个函数当整型自变量n趋向于无穷大时,两者的比值是一个不等于0的常数。这么一来,就好计算了吧。第(1)题中两个函数的最高次项都是n^3,因此当n→∞时,两个函数的比值是一个常数,所以这个关系式是成立的。 
第二章
一、选择题
,向第i个元素(1≤i≤n+1)之前插入一个新元素时,需向后移动个元素。
A. n-1 B. n-i+1 C. n-i-1 D. I
。
A. 一个有限序列,可以为空 B. 一个有限序列,不能为空
C. 一个无限序列,可以为空 D. 一个无限序列,不能为空
,设其长度为n,在任何位置上插入或删除操作都是等概率的, 删除一个元素时大约要移动表中的个元素。
A. n+1 B. n-1 C. (n-1)/2 D. n
,其地址。
A. 必须是连续的 B. 部分地址必须是连续的
C. 一定是不连续的 D. 连续与否均可以
(数据域为m),指针f指着将要插入的新结点(数据域为x),当x插在结点m之后时,只要先修改后修改p->link=f即可。
A. f->link=p; B. f->link=p->link;
C. p->link=f->link; D. f=nil;
,删除p所指的结点时需修改指针。
A. ((p->rlink) ->rlink) ->link=p; p->rlink=(p->rlink) ->rlink;
B. (p->llink) ->rlink=p->rlink; (p->rlink) ->llink=p->llink;
C. p->llink=(p->llink) ->llink; ((p->llink) ->llink) ->rlink=p;
D. ((p->llink) ->llink) ->rlink=p; p->llink=(p->llink) ->llink;
,删除p所指的结点的前趋结点(若存在)时需修改指针。
A. ((p->llink) ->llink) ->rlink=p; p->llink=(p->llink) ->llink;
B. ((p->rlink) ->rlink) ->llink=p; p->rlink=(p->rlink) ->rlink;
C. (p->llink) ->rlink=p->rlink; (p->rlink) ->llink=p->llink;
D. p->llink=(p->llink) ->llink; ((p->llink) ->llink) ->rlink=p;
,每个结点所含指针的个数,链表分为单链表和。
A. 循环链表 B. 多重链表 C. 普通链表 D. 无头结点链表
,在查找成功的情况下,需平
均比较个结点。
A. n B. n/2 C. (n-1)/2 D. (n+1)/2
,已知*q结点是*p结点的前驱结点,若在*q和*p之间插入*s结点,
则执行。
A. s->next=p->n