数据结构习题1

else if (pivotpos>j) return(R,j,low,pivotpos-1);

else return quicksort(R,j,pivotpos+1,high); }

} //QuickSort

2. 解：

void selectsort(linklist head){

RecNode *p,*q,*s;

if(head->next)&&(head->next->next){ p=head->next;//p指向当前已排好序最大元素的前趋

while (p->next){ q=p->next;s=p;

while(q){ if (q->keykey) s=q; q=q->next; }//endwhile

交换s结点和p结点的数据;

p=p->next; }//endwhile

}//endif

}//endsort 3. 解：

void QuickSort(SeqList R,int low ,int high){ //对R[low..high]快速排序

int pivotpos;

if(high-low<=2){//若当前区内元素少于3个 //则进行直接插入排序 InsertSort(R,low,high); }else{ pivotpos=midPartion(R,low,high);

QuickSort(R,low,pivotpos-1); QuickSort(R,pivotpos+1，high);

}

}//QuickSort

int midPartion(SeqList R,int i, int j){ //三者取中规则定基准

if(R[(i+j)/2].key>R[i].key){ 交换R[(i+j)/2]和R[i]; }

if(R[i].key>R[j].key) { 交换R[i]和R[j];} if(R[i].key)

20

}

21

提

习

一、选择题：

高

题

篇

一

1、研究数据结构就是研究 。

A、数据的逻辑结构 B、数据的存储结构

C、数据的逻辑结构和存储结构 D、 数据的逻辑结构、存储结构及其数据在运算上的实现 2、以下属于逻辑结构的是 。

A、顺序表 B、哈希表 C、有序表 D、单链表 3、具有线性结构的数据结构是 。

A、图 B、树 C、广义表 D、栈 4、数据的 包括集合、栈、树和图结构４种基本类型 A、存储结构 B、逻辑结构 C、基本运算 D、算法描述 5、下面程序的时间复杂度为 。 for (I=0;I

for (j=0;j

A、O(m2) B、O(n2) C、O(m×n) D、O( m+n) 6、一个递归算法必须包括___ ___。

A、递归部分 B、终止条件和递归部分 C、迭代部分 D、终止条件和迭代部分 7、以下说法正确的是___ ___。 A、数据元素是数据的最小单位 B、数据项是数据的基本单位

C、数据结构是带有结构的各数据项的集合

D、一些表面上很不相同的数据可以有相同的逻辑结构

二、填空题

1、从一维数组a[n]中顺序查找出一个最大值元素的平均时间复杂性为 ，读取一个二维数组b[m,n]中任一元素的时间复杂性为 。

2、线性结构中元素之间存在 关系，树形结构中元素之间存在 关系，图形结构中元素存在 关系，而集合结构中元素之间不存在 关系。

3、数据结构是研究数据的 和 以及它们之间的相互关系，并对这种结构定义相应的 并设计出相应的 。 4、通常从___ __、__ ___、_ ____、__ ___等4个方面评价算法（包括程序）的质量。

5、数据的___ __结构与数据元素本身的内容和形式无关。

6、程序段“I=1;while(I<=n) I=I*2;”的时间复杂性为___ __。

参考答案：

一、选择题：1、D 2、C 3、D 4、B 5、C 6、B 7、D

二、填空题： 1、O(N) O(1) 2、一对一 一对多 多对多 逻辑 3、物理结构 逻辑结构 算法 算法 4、正确性 易读性 健壮性 高效性 5、逻辑 6、O(log2n)

22

习题二

一、选择题：

1、线性表是具有n个_____的有限序列。

A、表元素 B、字符 C、数据元素 D、数据项 E、信息项 2、若长度为n的线性表采用顺序存储结构，在其第Ｉ个位置插入一个新元素算法的时间复杂度为______。

A、O (log2n) B、O(1) C、O(n) D、O (n)

3、已知指针p单链表中某一结点，将新生成的由s所指结点加到p所指结点之后，其语句应为_____。

A、 s-> next=p+1; p->next=s; B、 (*p).next=s;(*s).next=(*p).next; C、 s->next=p->next;p->next=s->next; D、 s->next=p->next;p->next=s;

4、将两个各有n个元素的有序表归并成一个有序表，其最少的比较次数是_____。 A、n B、2n-1 C、2n D、n-1 5、线性表Ｌ＝(a1, a2,?, an)，下列说法正确的是_____。 A、每个元素都有一个直接前驱和一个直接后继 B、线性表中至少要有一个元素

C、表中诸元素的排列顺序必须是由小到大或由大到小

D、除第一个和最后一个元素外，其余每个元素都有一个且仅有一个直接前驱和直接后继 6、对单链表表示法，以下说法错误的是_____。 A、数据域用于存储线性表的一个数据元素

B、指针域（或链域）用于存放一个指向本结点所含数据元素的直接后继所在结点的指针 C、所有数据通过指针的链接而组织成单链表

D、NULL称为空指针，它不指向任何结点只起标志作用

7、若给定有n个元素的向量，则建立一个有序单向链表的时间复杂性的量级是 。 A、Ｏ(1) B、O(n) C、O (n2) D、O (log2n) 8、单链表的主要优点是_____。

A、便于随机查询 B、存储密度高

C、逻辑上相邻的元素在物理上也是相邻的 D、插入和删除比较方便 9、对一个具有n个元素的线性表，建立其单链表的时间复杂度为_____。 A、O (n) B、O (1) C、O(n2) D、O(nlog2n) 10、循环链表的主要优点是_____

A、不再需要头指针

B、已知某结点位置后能容易找到其直接前趋 C、在进行插入、删除运算时能保证链表不断开 D、从表中任一结点出发都能扫描整个链表

11、对顺序表的优缺点，以下说法错误的是_____。 A、无需为表示结点间的逻辑关系而增加额外的存储空间 B、可以方便地随机存取表中的任一结点

C、插入和删除运算较为方便

D、由于要求占用连续空间，所以存储分配只能预先进行（静态分配） 二、填空题

2

23