计算机图形学经典试题

1、一1设线性表有n个元素，以下操作中，_a_在顺序表上实现比在链表上实现效率更高。 a. 输出第i（1in) 个元素的值 b. 交换第1个元素与第2个元素的值 c. 顺序输出这n个元素的值 d. 输出与给定值x相等的元素在线性表的序号二2设n个元素进栈序列是1，2，3，n，其输出序列是p1, p2, p3,，pn，若p1=3，则p2的值为（ c ）。 a.一定是2 b.一定是1 c.不可能是1 d.以上都不对3栈和队列，abcdefg先进栈，出来再进队列，出队列的顺序为bdcfeag，问栈至少需要多少空间（ a ）。 a.3 b.4 c.5 d.74在解决计算机主机与打印机之间速度不匹配问题时通

2、常设置一个打印数据缓冲区，主机将要输出的数据一次写入该缓冲区，而打印机则从该缓冲区中取出数据打印。该缓冲区应该是一个（ b ）结构。 a.栈 b.队列 c.数组 d.线性表5若用单链表来表示队列，下面几种数据结构中，最合适的选择是（ b ）。 a.带尾指针的非循环链表 b.带尾指针的循环链表 c.带头指针的非循环链表 d.带头指针的循环链表6若循环队列以数组q0.m-1作为其存储结构，变量rear表示循环队列中的队尾元素的实际位置，其移动按rear=(rear+1) %m进行，变量length表示当前循环队列中的元素个数，则循环队列的队首元素的实际位置（d ）。 a.rear-length b

3、.(rear-length+m)%m c.m-length d.(1+rear+m-length) %m 7 已知有一维数组a0.m*n-1，若要对应为m行、n列的矩阵，则下面的对应关系( c )可将元素ak(0k<m*n)表示成矩阵的第i行、第j列的元素(1i<m, 1j<n)。 a. i=k/n+1，j=k%m+1 b. i=k/m+1，j=k%m+1 c. i=k/n+1，j=k%n+1 d. i=k/m+1，j=k%n+1 8将一个a1.100，1.100的三对角矩阵，按行优先存入一维数组b1.298中，a中元素a66,65(即该元素下标i=66，j=65)，在b数组

4、中的位置k为( b )。 a.198 b.195 c.197 d.1969稀疏矩阵的三元组存储方法（ c ）。 a.实现转置算法很简单，只需将每个三元组的行标和列标交换 b.是一种链式存储方法 c.矩阵的非零元素个数和位置在操作过程中变化不大时较有效 d.比十字链表法更高效。三10完全二叉树第6层有8个叶子结点，完全二叉树最多有（ c ）结点。 a.100 b.39 c.111 d.12011在一棵完全二叉树中，其根的序号为1，（ a ）可判定序号为p和q的两个结点是否在同一层。 a. ëlog2pû= ëlog2qû b. log2p= log2q c

5、. ëlog2pû+1= ëlog2qû d. ëlog2pû= ëlog2qû+1 12在二叉树的顺序存储中，每个结点的存储位置与其父结点、左右子树结点的位置都存在一个简单的映射关系，因此可与三叉链表对应。若某二叉树共有n个结点，采用三叉链表存储时，每个结点的数据域需要d个字节，每个指针域占用4个字节，若采用顺序存储，则最后一个结点下标为k（起始下标为1），那么（ a ）时采用顺序存储更节省空间。 a.d<12n/(k-n) b. d>12n/(k-n) c. d<12n/(k+n) d. d&

6、gt;12n/(k+n)四13无向图中一个顶点的度是指图中（c ）。 a.通过该顶点的简单路径数 b.通过该顶点的回路数 c.与该顶点相邻的顶点数 d.与该顶点连通的定点数。14一个具有n(n>0)个顶点的连通无向图至少有（ c ）条边。 a.n+1 b.n c.n/2 d. n-11简单无向图的邻接矩阵式对称的，可以对其进行压缩存储。若无向图g有n个结点，其邻接矩阵为a1.n, 1.n，且压缩存储在b1.k中，则k的值至少为（d ）。若按行压缩存储对称矩阵的上三角元素，则当n=10时，边(v6, v3)的信息存储在b （ c ） 中。 (1)a.n(n+1)/2 b. n2/2 c.(

7、n-1)(n+1)/2 d.n(n-1)/2 (2)a.18 b. 19 c. 20 d.2115一个含有n个顶点和e条边的简单无向图，在其邻接矩阵存储结构中共有（ d ）个零元素。 a.e b. 2e c. n2-e d. n2-2e16若采用邻接矩阵来存储简单有向图，则其某一个顶点i的入度等于该矩阵（ d ）。 a.第i行中值为1的元素个数 b.所有值为1的元素个数 c.第i行及第i列中值为1的元素总个数 d.第i列中值为1的元素个数五17在有11个元素的有序表a1，11中进行折半查找(low+high）/2)中，查找元素a11时，被比较的元素的下标依次是（ d ）。 a. 6，8，10，11 b. 6，9，10，11 c. 6，7，9，11 d. 6，8，9，1118在常用的描述二叉排序树的存储结构中，关键字值最大的结点（ b ）。 a.左指针一定为空 b.右指针一定为空 c.左右指针均为空 d.左右指针均不空19在平衡二叉树中，（ c ）。 a.任意结点的左、右子树结点数目相同 b.任意结点的左、右子