习题2
1. 填空题
(1)在一个单链表中,已知每个结点包含data和next两个域,q所指结点是p所指结点的直接前驱,若在q和p之间插入s所指结点,则执行(___________)和(___________)操作。
答案:q->next = s; s->next = p; 或 s->next=q->next; q->next = s;
(2)表长为n的顺序表,当在任何位置上插入或删除一个元素的概率相等时,插入一个元素所需移动元素的平均个数为(___________),删除一个元素需要移动元素的平均个数为(___________)。 答案:n/2 (n-1)/2
(3)表长为0的线性表称为(___________)。 答案:空表
(4)动态内存管理是操作系统的基本功能之一,其作用是响应用户程序对内存的(___________)和(___________)请求。 答案:申请 释放
(5)顺序表多采用(___________)实现的,是一种随机存取结构,对表中任意结点存取操作的时间复杂度为(___________)。而查找链表中的结节,需要从头指针起顺着链扫描才能得到,平均时间复杂度为(___________)。因此,若线性表的操作主要是进行查找,很少进行插入或删除操作时,采用(___________)表比较合适。 答案:数组 O(1) O(n) 顺序
(6)在链表某个位置上进行插入和删除操作,只需要修改(___________)即可,而无须移动大量元素,操作的时间复杂度为(___________)。而在顺序表中进行插入和删除操作,往往要移动大量元素,平均移动元素的数目为(___________),平均时间复杂度为(___________)。因此,若对线性表进行频繁的插入和删除操作时,采用(___________)表相对合适。若插入和删除主要发生在表头和表尾,则采用(___________)表更为合适。 答案:指针 O(1) 表长的一半 O(n) 链 循环链
(7)静态链表一般采用(___________)存储的链表结构。 答案:数组 (8)对于32位计算机环境,若单链表中的数据类型为整性,则其存储密度为(___________),而若为双链表,则存储密度为(___________)。若采用顺序表存储数据,则其存储密度为(___________)。 答案:50% 33% 1
(9)向量是最常用的容器,STL中向量使用(___________)实现,因此向量具有(___________)表的所有特点,可以快速随机存取任意元素。 答案:数组 顺序
(10)操作系统在运行之初,有一块很大的连续内存块供用户程序申请,通常称之为内存池或(___________)。 答案:堆
(11)循环链表与单链表的区别仅仅在于其尾结点的链域值不是(___________),而是一个指向(___________)的指针。 答案:NULL(或空指针) 头结点 2. 选择题
1
(1)线性表的顺序存储结构是一种( )的存储结构,线性表的链式存储结构是一种( )的存储结构。 A. 随机存取 索引存取 B. 顺序存取 随机存取 C. 随机存取 顺序存取 D. 索引存取 散列存取
(2)在双向链表p所指结点之前插入s所指结点的操作是( )。 A. p->left=s; s->right=p; p->left->right =s; s->left=p->left; B. p->right=s; p->right->left=s; s->left=p; s->right=p->right; C. s->right=p; s->left=p->left; p->left=s; p->left->right =s; D. s->right=p; s->left=p->left; p->left->right =s; p->left=s;
(3)若链表是利用C++指针来存储结点的地址,结点空间的分配和收回都是由操作符new和delete动态执行的,则称该链表为( )链表 A. 单向 B. 双向 C. 静态 D. 动态
(4)将线性表存储到计算机中可以采用多种不同的方法,按顺序存储方法存储的线性表称为( ),按链式存储方法存储的线性表称为( )。
A. 数组 单链表 B. 顺序表 链表 C. 向量 静态链表 D. 静态链表 动态链表 (5)( )是STL中线性表的链式存储形式,STL标准库中一般采用( )实现。
A. vector 数组 B. list 单链表 C. list 双向循环链表 D. vector 单链表
(6)顺序表的类型定义可经编译转换为机器级。假定每个结点变量占用k(k>=1)个字节,b是顺序表的第一个存储结点的第一个单元的内存地址,那么,第i个结点ai的存储地址为( )。 A. b+ki B. b+k(i-1) C. b+k(i+1) D. b-1+ki (7)在循环链表中,若不使用头指针而改设为尾指针(rear),则头结点和尾结点的存储位置分别是( )。
A. real和rear->next->next B. rear->next 和rear C. rear->next->next和rear D. rear和rear->next
(8)有时为了叙述方便,可以对一些概念进行简称,以下说法错误的是( )。 A. 将“指针型变量”简称为“指针” B. 将“头指针变量”简称为“头指针”
C. 将“修改某指针型变量的值” 简称为“修改某指针” D. 将“p中指针所指结点” 简称为“P值” (9)以下说法错误的是( )。
A. 对循环链表来说,从表中任一结点出发都能通过向前或向后操作而扫描整个循环链表。 B. 对单链表来说,只有从头结点开始才能扫描表中全部结点。 C. 双链表的特点是找结点的前趋和后继都很容易。
D. 对双链表来说,结点*P的存储位置既存放在其前趋结点的后继指针域中,也存放在它的后继结点的前趋指针域中。
(10)以下说法正确的是( )。
A. 顺序存储方式的优点是存储密度大、且插入、删除运算效率高。 B. 链表的每个结点中都至少包含一个指针。 C. 线性表的顺序存储结构优于链式存储结构。
D. 顺序存储结构属于静态结构,链式结构属于动态结构。
2
说明:静态链表是链式结构,但属于静态存储结构.链表的每个结点中都至少包含一个指针。原题中,“恰好”改为了”至少”。
(11)单链表中,增加头结点的目的是为了 ( )
A. 使单链表至少有一个结点 B. 标示表结点中首结点的位置
C. 方便运算的实现 D. 说明单链表是线性表的链式存储实现
3. 程序选择题
(1)已知L指向带表头结点的非空单链表的头结点,且P结点既不是首结点,也不是尾结点,试从下列提供的答案中选择合适的语句序列:
a.删除P结点的直接后继结点的语句序列是(___________) b.删除P结点的直接前驱结点的语句序列是(___________) c.删除P结点的语句序列是(___________) d.删除首结点的语句序列是(___________) e.删除尾结点的语句序列是(___________) (1) delete Q; (2) Q = P (3) L = L->next (4) P = L (5) Q = P->next (6) P->next = P 答案: a. 5 8 1
b. 2 4 14 5 8 1 c. 2 4 10 8 1 d. 4 5 8 1 e. 4 13 5 8 1
(2)已知p结点是某双向链表的中间结点,试从下面语句((1)~(18))中选择合适的语句序列,完成a~e要求的操作。
a. 在p结点后插入s结点的语句序列是________________________________。 b. 在p结点前插入s结点的语句序列是________________________________。 c. 删除p结点的直接后继结点的语句序列是_____________________________。
d. 删除p结点的直接前驱结点的语句序列是_____________________________。 e. 删除p结点的语句序列是____________________________。
(8) P->next = P->next->next (9) P = P->next (10) while(P->next != Q) P = P->next; (11) while(P != NULL) P = P->next; (12) while(Q->next != NULL) { P = Q ; Q = Q->next;} (13) while(P->next->next != NULL) P = P->next; (7) P = P->next->next (14) while(P->next->next != Q) P = P->next; 3
北邮C++数据结构课后习题 习题2参考答案
![](/skin/haowen/images/icon_star.png)
![](/skin/haowen/images/icon_star.png)
![](/skin/haowen/images/icon_star.png)
![](/skin/haowen/images/icon_star.png)