数据结构习题集和答案.doc

第1章 绪论 1、填空题 1.常见的数据结构有_线性__结构，__树形___结构，__图形__结构等三种。 2.常见的存储结构有__顺序存储_______结构，__链式存储____结构等两种。 3.数据的基本单位是_数据元素___，它在计算机中是作为一个整体来处理的。 4.数据结构中的结构是指数据间的逻辑关系，常见的结构可分为两大类，__线性结构____和__非线性结构___。 2、应用题 1、给出以下算法的时间复杂度. void fun int n int i 1,k 100; while i n k k+1; i i+2; 时间复杂度为____O（n）_____。 2、给出以下算法的时间复杂度. void fun2 int n int i 1,k 100; while i n i i*10; k k+1; 时间复杂度为____O（log n）___________。 第2章 线性表 1、填空题 1. 线性表按照存储结构不同主要有两种实现方式，一种是__顺序_表，另一种是___链___表。 2.顺序表采用__随机___访问机制对数据元素进行访问。 3.若在单链表结点p的后面插入一个新的结点s，则其操作序列为: ①____s- next p- next_____________； ②____p- next s___________________； 4.在单向链表中，若要删除某个结点p，一般要找到__p的前趋__结点，才能实现该操作。 2、选择题 将两个各有n个元素的有序表归并成一个有序表，其最少的比较次数是 A 。 A n B 2n－1 C 2n D n-1 在单链表中，如果在结点p之后插入一个新结点s，其操作为 A 。 （A）s- next p- next; p- next s; （B）p- next s; s- next p- next; （C）s- next p; p- next s- next; （D）p- next s; s- next p; 3.若长度为n的线性表采用顺序存储结构，在其第i个位置一个元素的算法的时间复杂度为 。 1≤i≤n A．O 0 B．O 1 C.O n D．O n2 若长度为n的线性表采用顺序存储结构，在其第i个位置一个新元素 B? 。 1≤i≤n+1 A． B． C. i D．struct LinkNode LinkNode *next; int data; ; 请根据述函数的功能写程序。 void Insert LinkNode *h,LinkNode *s //h指向链表的头结点（即使链表中没有元素，头结点也存在。） //链表中元素已经递增有序 //函数功能为将结点s插入到链表h中。插入后链表仍然保持递增的顺序 LinkNode *p,*q;//q指向p的前驱 q h; p h- next; while p if p- data s- data //寻找到插入点位置，插入s q- next s; s- next p; return; else q p; 1分 p p- next; 1分 //当表中没有比s大的结点时，插入到表尾 s- next q- next; 2分 q- next s; 2分 2、设顺序表L是一个递增有序表，试写一算法，将x插入L中，并使L仍是一个有序表表结构#define ListSize 100 // 假定表空间大小为100struct Sqist int elem[ListSize]; // 数组elem用于存放表int length; // 当前的表长度 ;//以上为表结构 InsertIncreaseList SqList L ,int x int i;　if Llength ListSize cout ”OVERFLOW”; //判断是否溢出 　for i Llength ; i 0 L.elem[ i-1 ] x ; i-- 　　　L[ i ] L.elem[ i-1 ] ; // 比较并移动元素　L[ i ] x; //插入x 　Llength++; //表长增1  /////// 3、单链表中结点的结构如下所示： typedef struct node