Artigo sobre Estrutura de Dados (1)
1. Perguntas de múltipla escolha (2 pontos por pergunta, 20 pontos no total)
1. As características comuns de pilhas e filas são ( ).
A. Permitir apenas a inserção e exclusão de elementos no ponto final
B. Todos primeiro a entrar, último a sair
C. É tudo primeiro a entrar, primeiro a sair
D. Não há terreno comum
2. A fila armazenada de forma ligada é inserida ao realizar a operação de inserção ( ).
A. Apenas o ponteiro cabeça é modificado B. Os ponteiros cabeça e cauda devem ser modificados
C. Modificar apenas o ponteiro de cauda D. Os ponteiros de cabeça e cauda podem precisar ser modificados
3. Qual das seguintes estruturas de dados é uma estrutura não linear? ( )
A. Fila B. Pilha C. Tabela linear D. Árvore binária
4. Se existe um arranjo bidimensional A[m][n], assumindo que A[0][0] está armazenado em 644 (10), e A[2][2] está armazenado em 676 (10), cada elemento ocupa um espaço, onde está armazenado A[3][3][3](10)? A nota de rodapé (10) indica que está expressa em decimal.
A.688 B.678 C.692 D.696
5. Árvores são melhor usadas para representar ( ).
A. Elementos de dados ordenados B. Elementos de dados não ordenados
C. Dados com relações hierárquicas ramificadas entre elementos D. Dados sem conexão entre elementos
6. O número máximo de nós na k-ésima camada da árvore binária é ( ).
A.2k-1 B.2K+1 C.2K-1 D. 2k-1
7. Se houver uma tabela ordenada de 18 elementos armazenada em um array unidimensional A[19], o primeiro elemento for colocado em A[1], e agora uma busca binária for realizada, então o índice da sequência de comparação para encontrar A[3] é ( )
A. 1,2,3 B. 9,5,2,3
C. 9,5,3 D. 9,4,2,3
8. Ordenar rapidamente os arquivos de n registros, e o espaço de armazenamento auxiliar necessário é aproximadamente o mesmo
A. O(1) B. O(n) C. O(1og2n) D. O(n2)
9. Para tabelas lineares (7, 34, 55, 25, 64, 46, 20, 10) para armazenamento de hash, se H(K)=K%9 for selecionado como função de hash, há elementos ( ) com endereço de hash 1.
A.1 B.2 C.3 D.4
10. Um grafo não direcionado com 6 nós, e o grafo deve ter pelo menos ( ) arestas para garantir um grafo conexo.
A.5 B.6 C.7 D.8
2. Preencher as lacunas (1 ponto por branco, 26 pontos no total)
1. A qualidade do algoritmo geralmente é avaliada sob quatro aspectos: _________, _________, _________ e _________.
2. A complexidade temporal de um algoritmo é (n3+n2log2n+14n)/n2, e sua ordem de magnitude é expressa como ________.
3. Assumindo que a tabela generalizada de uma árvore é representada como A(C,D(E,F,G),H(I,J)), então o número de nós contidos na árvore é __________, a profundidade da árvore é ___________ e o grau da árvore é _________.
4. O valor da fórmula do sufixo 9 2 3 +- 10 2 / - é __________. A fórmula do sufixo correspondente à fórmula do meio (3+4X)-2Y/3 é _______________________________.
5. Se uma árvore binária for armazenada com uma lista encadeada, cada nó tem dois ponteiros para o filho esquerdo e o filho direito, além do campo de dados. Nessa estrutura de armazenamento, a árvore binária com n nós possui um total de ________ campos de ponteiros, dos quais ________ campos de ponteiros armazenam endereços e ________________ ponteiros são ponteiros vazios.
6. Para um grafo direcionado e um grafo não direcionado com n vértices e arestas em barra E, há _______ e ________ nós de aresta em sua tabela de adjacência correspondente, respectivamente.
7. A rede AOV é um grafo ___________________.
8. Em um grafo completo não direcionado com n vértices, há ________ arestas, e em um grafo completo direcionado com n vértices, há ________ arestas.
9. Assumindo que uma tabela linear é (12,23,74,55,63,40), se os elementos do mesmo resto se tornarem uma subtabela de acordo com a condição Key % 4, as quatro subtabelas obtidas são ____________________________, ___________________, _______________________ e __________________________.
10. No processo de inserir elementos em uma árvore B_, se o nó raiz da árvore for finalmente dividido, a altura da nova árvore é ___________ do que a da árvore original.
11. No processo de ordenação de heap, a complexidade temporal de peneirar qualquer nó de ramo é ________, e a complexidade de tempo de todo o processo de ordenação de heap é ________.
12. Na ordenação rápida, ordenação por heap e ordenação por fusão, _________ ordenação é estável.
Artigo sobre Estrutura de Dados (2)
1. Perguntas de múltipla escolha (24 pontos)
1. A seguinte descrição das tabelas lineares está incorreta ().
(A) Tabelas lineares são armazenadas sequencialmente e devem ocupar um espaço de armazenamento contíguo
(B) Tabelas lineares são encadeadas e não ocupam um espaço contínuo de armazenamento
(C) Tabelas lineares são implementadas com armazenamento em cadeia para facilitar operações de inserção e exclusão
(d) Tabelas lineares são implementadas com armazenamento sequencial para facilitar operações de inserção e exclusão
2. Suponha que o número total de nós folha na árvore de Huffman seja m, e se uma lista binária encadeada for usada como estrutura de armazenamento, há um total de ( ) campos de ponteiros vazios na árvore de Huffman.
(A) 2m-1 (B)2m (C)2m+1 (D)4m
3. Se os ponteiros cabeça e cauda da fila sequencial Q[0:M-1] forem F e R, respectivamente, o ponteiro cabeça F sempre aponta para a posição anterior do elemento cabeça, e o ponteiro cauda R sempre aponta para a posição atual do elemento cauda, então o número de elementos na fila de loop é ( ).
(A) R-F (B) F-R (C) (R-F+M)%M (D) (F-R+M)%M
4. Se a sequência de percurso de ordem intermediária de uma árvore binária for ABCD e a sequência anterior for CABD, então a sequência obtida ao percorrer a árvore binária na ordem seguinte é ().
(A) BADC (B)BCDA (C) CDAB (D) CBDA
5. Suponha que existam n vértices em um grafo completamente não direcionado, então existem ( ) arestas no grafo completamente não direcionado.
(A) n(n-1)/2 (B) n(n-1) (C) n2 (D) n2-1
6. Suponha que existam 2000 nós em uma árvore binária, então a altura mínima da árvore binária é ( ).
(A) 9 (B) 10 (C) 11 (D) 12
7. Suponha que existam n vértices em um grafo direcionado, então existem ( ) nós de cabeçalho na tabela de adjacência correspondentes ao grafo direcionado.
(A) n-1 (B) n (C) n+1 (D) 2n-1
8. Defina um conjunto de sequências iniciais de palavras-chave de registro (5, 2, 6, 3, 8), e o resultado de uma ordenação rápida baseada na primeira palavra-chave de registro 5 é ( ).
(A) 2,3,5,8,6 (B) 3,2,5,8,6
(C) 3,2,5,6,8 (D) 2,3,6,5,8
2. Preencher as lacunas (24 pontos)
1. Para aplicar efetivamente a tecnologia de busca HASH, dois problemas que precisam ser resolvidos são ____________________ e __________________________.
2. A função do segmento de programa seguinte realiza os dados x na pilha e exige que a instrução correta seja preenchida no sublinhado.
typedefstruct {int s[100]; int top; } stack quadrado;
empurrar vazio (sqstack&stack,int x)
{
if (stack.top==m-1) printf("overflow");
senão {____________________; _________________; }
}
3. A sequência obtida ao percorrer a árvore binária de ordenação na ordem intermediária é uma sequência ___________ (preenchida ordenada ou não ordenada).
4. A pior complexidade temporal da ordenação rápida é ___________, e a complexidade média de tempo é __________.
5. Se o número de nós com grau 0 em uma árvore binária for N0 e o número de nós com grau 1 for N1, então o número de nós com grau 2 na árvore binária é _________; Se uma lista binária ligada for usada como estrutura de armazenamento da árvore binária, _______ há campos de ponteiro vazios na árvore binária.
6. Suponha que o número de vértices e arestas em um certo grafo não direcionado seja n e e, respectivamente, e a soma dos graus de todos os vértices seja d, então e = _______.
7. Se a sequência inicial de palavras-chave do registro for (55, 63, 44, 38, 75, 80, 31, 56), então o heap inicial estabelecido pelo método de triagem é ___________________________.
8. Sabe-se que a estrutura de armazenamento de tabelas de adjacência de um grafo direcionado é a seguinte: A partir do vértice 1, a sequência de saída da travessia DFS é:
, a sequência de saída do percurso BFS é
Artigo sobre Estrutura de Dados (3)
1. Perguntas de múltipla escolha (1 ponto por pergunta, 20 pontos no total)
1. Se a forma binária de uma estrutura de dados for expressa como A=(D,R),D={01,02,03,04,05,06,07,08,09}, R={r},r={<01,02>,<01,03>,<01,04>,<02,05>,<02,06>,<03,07>,<03,08>,<03,09>}, então a estrutura de dados A é ( ).
(A) Estrutura linear (B) Estrutura em árvore (C) Estrutura física (D) Estrutura gráfica
2. O complexo temporal do programa a seguir é ()
para (i=1,s=0; i<=n; i++) {t=1;for(j=1;j<=i; j++) t=t*j; s=s+t; }
(A) O(n) (B) O(n2) (C) O(n3) (D) O(n4)
3. Defina a variável de ponteiro p para apontar para o nó A em uma única lista encadeada; se você excluir o nó A em uma única lista encadeada, precisa alterar a sequência de operações do ponteiro para ().
(A) q=p->próximo; p->data=q->data; p->próximo=q->próximo; livre(q);
(B) q=p->próximo; q->data=p->data; p->próximo=q->próximo; livre(q);
(C) q=p->próximo; p->próximo=q->próximo; livre(q);
(D) q=p->próximo; p->data=q->data; livre(q);
4. Se houver n palavras-chave de registro a serem ordenadas, ( ) unidades auxiliares de registro são necessárias na ordenação do heap.
(A) 1 (B) n (C) nlog2n (D) n2
5. Se as palavras-chave iniciais do registro de palavras-chave forem (20, 15, 14, 18, 21, 36, 40, 10), então o resultado após o final de uma ordenação rápida foi registrado com 20 como benchmark é ( ).
(A) 10,15,14,18,20,36,40,21
(B) 10,15,14,18,20,40,36,21
(C) 10,15,14,20,18,40,36,2l
(D) 15,10,14,18,20,36,40,21
6. Suponha que existam n nós na árvore binária de ordenação, então o comprimento médio de busca na árvore binária é ( ).
(A) O(1) (B) O(log2n) (C) (D) O(n2)
7. Suponha que existam n arestas de vértice e no grafo não direcionado G, então o número de nós cabeçalho e nós da tabela na tabela de adjacência correspondente é ( ).
(A) n,e (B) e,n (C) 2n,e (D) n,2e
8. Suponha que existam n vértices em um grafo de conexão forte, então existem pelo menos ( ) arestas no grafo de conexão forte.
(A) n(n-1) (B) n+1 (C) n (D) n(n+1)
9. Existem 5000 palavras-chave de registro a serem ordenadas; se você precisar usar o método mais rápido para selecionar as 10 menores palavras-chave de registro, pode usar o seguinte método ( ) para alcançar esse propósito.
(A) Ordenação rápida (B) Ordenação por heap (C) Ordenação por mescla (D) Ordenação por inserção
10. Os seguintes quatro tipos de ( ) têm a maior complexidade espacial.
(A) Classificação por inserção (B) Ordenação por bulhas (C) Classificação por heap (D) Ordenação por fusão
2. Preencher as lacunas (1 ponto por branco, 20 pontos no total)
1. A estrutura física dos dados inclui principalmente duas situações: _____________ e ______________.
2. Se houver 500 nós em uma árvore binária completa, a profundidade da árvore binária é __________; Se você usar uma lista binária encadeada como estrutura de armazenamento para a árvore totalmente binária, ___________ há campos de ponteiro vazios.
3. Se a sequência de entrada for 1, 2, 3, então ___________ sequências de saída diferentes podem ser obtidas após a ação da pilha.
4. Se a matriz de adjacência A[n][n] for usada como estrutura de armazenamento para o grafo G, então a soma de todos os elementos na linha i na matriz de adjacência é igual ao ________ do vértice i, e a soma de todos os elementos na coluna i é igual ao ________ do vértice i.
5. Se houver n nós na árvore de Huffman, há ________ nós com grau 1 na árvore de Huffman.
6. Se houver n vértices e no grafo direcional G com arestas direcionais, e a soma de todos os vértices que entram em graus for d, então a relação entre e e d é _________.
7. __________ percorrer os nós na árvore binária de ordenação pode obter uma sequência incremental de palavras-chave (preenchidas, do meio ou posterior).
8. Se houver 100 elementos na tabela de consulta, se você usar o método de busca dicotômica para encontrar o elemento de dados X, precisa compará-lo até ________ vezes para determinar se o elemento X está na tabela de consulta.
9. Seja uma pilha com estrutura de armazenamento sequencial ou uma pilha com uma estrutura de armazenamento em cadeia, a complexidade temporal das operações dentro e fora da pilha é ____________.
10. Uma árvore binária completa com n nós, se numerada de cima para baixo e da esquerda para a direita começando de 1, o nodo pai do i-ésimo nó é numerado ____________, e o número do nó filho direito é ___________.
11. Se o conjunto inicial de palavras-chave registradas for (72, 73, 71, 23, 94, 16, 5), então o resultado de uma ordenação rápida baseada na palavra-chave de registro 72 é ___________________________.
12. Se existe um conjunto de arestas direcionadas no grafo direcional G E={<1,2>,<2,3>,<1,4>,<4,2>,<4,3>}, então uma sequência topológica do grafo é ____________________.
13. O algoritmo a seguir implementa a palavra-chave com valor x na lista de hashes sequencial, por favor, preencha a instrução correta no sublinhado.
struct record{int key; em outros; };
inthashsqsearch(hashtable de registro struct[ ],int k)
{
inti,j; j=i=k % p;
enquanto (hashtable[j].key!=k&&hashtable[j].flag!=0){j=(____) %m; se (i==j) return(-1); }
se (_______________________ ) retorno (j); caso contrário, retorna (-1);
}
14. O algoritmo a seguir implementa o valor-chave k na árvore binária de ordenação, por favor, preencha a instrução correta no sublinhado.
typedefstruct node{int key; nó de struct *lchild; nó struct *rchild; }bitree;
bitree *bstsearch(bitree *t, int k)
{
se (t==0) retorna(0); senão enquanto (t!=0)
if (t->key==k)_____________; caso contrário, se (t->chave>k) t=t->lchild; else_____________;
}
Prova de estrutura de dados (1) Consulte a resposta
1. Perguntas de múltipla escolha (2 pontos por pergunta, 20 pontos no total)
1.A 2.D 3.D 4.C 5.C 6.D 7.D 8.C 9.D 10.A
2. Preencher as lacunas (1 ponto por branco, 26 pontos no total)
1. Correção, legibilidade, resistência e alta eficiência
2.O(n)
3.9 3 3
4.-1 3 4 X * + 2 Y * 3 / -
5,2n n-1 n+1
6.e 2e
7. Direcional e não circuitual
8.n(n-1)/2 n(n-1)
9.（12，40） （ ） （74） （23,55，63）
10. Adicionar 1
11.O(log2n) O(nlog2n)
12. Consolidação
As respostas para outras perguntas do teste podem ser vistas:
Turistas, se quiserem ver o conteúdo oculto deste post, por favor Resposta
|
Publicado em 25/11/2014 12:46:30
|
|
|
Publicado em 30/12/2014 00:10:55