数据结构课后习题.docVIP

习题一 一、单选题 1. 下列四种基本逻辑结构中，数据元素之间关系最弱的是 _，列队属于_____。 A.集合 B.线性结构 C.树形结构 D.图形结构 2. 线性结构各数据元素之间存在着_____的关系，图形结构数据元素之间存在____的关系。 A.无关 B.一对一 C.一对多 D.多对多 3. 在数据结构中，从逻辑上看可以把数据结构分为_____。 A.动态结构和静态结构 B.紧凑结构和非紧凑结构 C.线性结构和非线性结构 D.内部结构和外部结构 4. 算法中的基本操作重复执行的频度称为算法的______；除了考虑存储数据结构本身所占用的空间外，实现算法所用辅助空间的多少称为算法的______。 A.时间复杂度 B.空间复杂度 C.硬件复杂度 D软件复杂度 5．算法分析的目的是_① ，算法分析的两个主要方面是 ② 。 ① A .找出数据结构的合理性 B. 研究算法中的输入和输出关系 C. 分析算法的效率以求改进 D. 分析算法的易懂性和文档性 ② A. 空间复杂度和时间复杂度 B. 正确性 C. 可读性和文档性 D. 数据复杂性和程序复杂性 6. 计算机算法指的是_ ① ,它必具备输入、输出和_ ② 等五个特性。 ①A.计算方法 B. 排序方法 C. 解决问题的有限运算序列 D. 调度方法 ②A. 可行性、可移植性和可扩充性 B. 可行性、确定性和有穷性 C. 确定性、有穷性和稳定性 D. 易读性、稳定性和安全性 7. 线性表的逻辑顺序与存储顺序总是一致的，这种说法_____。 A. 正确 B. 不正确 8. 线性表若采用链式存储结构时，要求内存中可用存储单元的地址______。 A. 必须是连续的 B. 部分地址必须是连续的 C. 一定是不连续的 D. 连续或不连续都可以 二、填空题（将正确的答案填在相应的空中） 1．数据逻辑结构包括集合、____ ____、_____ ____和_________四种类 型，树形结构和图形结构统称为_______________。 2. 线性结构中，第一个结点__________前驱结点，其余每个结点有且仅有______个直接前驱结点；最后一个结点___________后继结点，其余每个结点有且仅有_____个直接后继结点。 3. 在树形结构中，树根结点没有______结点，其余每个结点有且只有______个前驱结点；叶子结点没有_____结点，其余每个结点的后继结点可以________。 4. 在图形结构中，每个结点的前驱结点数和后继结点数可以____________。 5. 线性结构中元素之间存在______关系，树形结构中元素直接存在______关系，图形结构中元素之间存在________关系。 6. 算法的五个重要特性是__________、__________、__________、________、_____________。 7. 下列程序段的时间复杂度是_________。 for(i=0; in; i++) for(j=0; jm; j++) a[i][j]=0; 8. 下列程序段的时间复杂度是_________。 i=s=0; while(sn) { i++; s+=I; } 9. 下列程序段的时间复杂度是_________。 s=0; for(i=0; in; i++) for(j=0; jn; j++) s+=b[i][j]; sum=s; 10. 下列程序段的时间复杂度是_________。 i=1; while(in) i=i*3; 习题二 填空题 在一个长度为n的向量的第i个元素（1=i=n）之前插入一个元素时，需向后移动_______个元素。 在一个长度为n的向量中删除第i个元素（1=i=n）时，需向前移动____个元素。 单链表是___________的链接存储表示。 在单链表中设置头结点的作用是在插入或删除第一个结点时不必对________进行处理。 在双链表中，每个结点有两个指针域，一个指向___________，另一个指向____________。 在一个单链表中p所指结点之后插入一个s所指结点时，应执行s-next=________和p-next_________的操作。 非空的循环单链表head的尾结点（由p所指向）满足条件______________。 单选题 不带头